Sliding Window - Longest - Two Pointers / Sliding Window

Problems
1

https://algo.monster/problems/subarray_sum_longest

2

In the template code, should we do inside the while loop: ans = max(ans, window) ? since the window is invalid there…

3

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
5 
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;
    }```
7

So its going to be O(n^2) ?
can we make it On(n)

8

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)

9

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;
}
10

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
11

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
13

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;
}
14

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
15

{100, 100, 100} and target=-10 fails with your solution.

16

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;
}
17

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.

18

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

19

Why the hell there is no place to take notes ? That would make it so easier to revise!