Sliding Window - Longest - Two Pointers / Sliding Window

https://algo.monster/problems/subarray_sum_longest

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

1 Like
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.