In the template code, should we do inside the while loop: ans = max(ans, window) ? since the window is invalid there…
Please add more test cases, it’s really hard to know whether solutions that differ to yours actually catch the edge cases properly, or even whether your code does in practice
public static int subarraySumLongest(List<Integer> nums, int target) {
LinkedList<Integer> list = new LinkedList<>();
int sum = 0;
int prev = 0;
int result = 0;
for (int i = 0; i < nums.size(); i++){
int current = nums.get(i);
if (current + sum <= target){
result = Math.max(result, list.size());
} else {
sum -= nums.get(prev);
list.removeFirst();
prev++;
}
sum+= current;
}
return result;
}```So its going to be O(n^2) ?
can we make it On(n)
I don’t think it is O(n^2) because that would mean there exists an array of inputs that will cause the inner while loop to execute n times for every iteration of the for loop. That cannot be possible because start index will never exceed the end index.
The only case where the inner while loop will execute O(n) times is when the end index reaches the last value and only the last value makes sum > target, but the while loop will only iterate n-1 times for that last iteration of the for loop.
ex: target = 20 nums=[1, 2, 3, 4, 20]
sum = 1 + 2 + 3 + 4 = 10 (at no iteration so far has the while loop executed because sum <= target
then
sum = 10 + 20 = 30 (then the while loop runs n-1 times to move start forward)
Solution I came up with, taking into account that the next longest has to also satisfy the condition that the subarray is longer than the previous longest
function subarraySumLongest(nums, target) {
// WRITE YOUR BRILLIANT CODE HERE
if(nums.length < 1) {
return nums[0] && nums[0] <= target ? 1 : 0
}
let start = 0
let end = 1
let max = 0
let curr_sum = 0
while(end < nums.length) {
curr_sum = curr_sum + nums[end]
if(curr_sum <= target) {
max = Math.max(end - start + 1, max)
end++
} else {
curr_sum -= nums[start]
start++
end++
}
}
return max;
}
If you provide a nums with length=1 then your check will fail at the beginning.
Here is the modified code:
arr_len = len(num_arr)
if arr_len == 0:
return 0
left_ptr, right_ptr = 0, 0
window_sum = 0
longest_sub_array_len = 0
while right_ptr < len(num_arr):
window_sum += num_arr[right_ptr]
if window_sum <= target:
longest_sub_array_len = max(right_ptr - left_ptr + 1, longest_sub_array_len)
right_ptr += 1
else:
window_sum -= num_arr[left_ptr]
left_ptr += 1
right_ptr += 1
return longest_sub_array_len
Here’s the solution that I came up with:
from typing import List
def subarray_sum_longest(nums: List[int], target: int) -> int:
window_sum, right = 0, 0
while window_sum <= target and right < len(nums):
window_sum += nums[right]
right += 1
if right > len(nums):
return 0
longest = right - 1
left = 0
while right < len(nums):
window_sum -= nums[left]
left += 1
while window_sum <= target and right < len(nums):
window_sum += nums[right]
right += 1
longest = max(longest, right - left - 1)
return longest
One more solution:
public int subarraySumLongest(List<Integer> nums, int target) {
int slow = 0, fast = 0, window = 0, length = nums.size(), max = Integer.MIN_VALUE;
while (fast < length) {
while (window < target) {
window += nums.get(fast);
fast++;
}
max = Math.max(max, fast - slow);
window -= nums.get(slow);
slow++;
}
return max;
}
The algorithm fails if we have negavite numbers:
subarraySumLongest([1, 2, 1, 0, 1, -8, -9, 0], 4); // returns 7, but actually it is 8
{100, 100, 100} and target=-10 fails with your solution.
My solution is a bit different.
I use left and right pointers as well, but instead of saving the max length every time, I just return right - left at the end.
function subarraySumLongest(nums, target) {
let left = 0, right = 0;
let currentSum = 0;
while (right < nums.length) {
currentSum += nums[right]
if (currentSum > target) {
currentSum -= nums[left++];
}
right += 1;
}
return right - left;
}
You’re right, but since the “Fixed Size Sliding Window” problem allows only non-negative values in the input array, I think the same applies to this problem.
I guess the mods should add this condition to the description on this page as well.
Isn’t this algo wrong?
it doesn’t work with negative number
1, 6, 3, 1, 2, 4, 5, -100
10
Output → 4
Expected → 8