Sliding window

Maintain a flexible constraint over contiguous data by inch-worming your pointers.

The idea

A sliding window is a specific type of two-pointer technique used for contiguous subarrays. Instead of recalculating a sum, product, or set of distinct elements from scratch for every possible subrange, we reuse the work from the previous range.

We expand the window on the right to add new elements, and if we violate a constraint (like "sum must be ≤ K"), we shrink the window from the left until the constraint is satisfied again. Both pointers only ever move forward, making it an amortized O(N) approach.

Target: Longest subarray with sum ≤ 10.

How it works

The standard template for a flexible window uses a for loop to expand the right pointer, and a while loop inside it to shrink the left pointer whenever the condition is broken.

def longest_subarray_sum(nums, k):
    left = 0
    curr_sum = 0
    best_len = 0
    
    for right in range(len(nums)):
        curr_sum += nums[right]
        
        # Shrink the window if constraint is violated
        while curr_sum > k:
            curr_sum -= nums[left]
            left += 1
            
        # Update best result now that window is valid
        best_len = max(best_len, right - left + 1)
        
    return best_len

Cost

Time Complexity O(N)

Space Complexity O(1)

Even though there is a while loop inside a for loop, each element is visited at most twice (once by Right, once by Left). This makes it amortized O(N) time.

Watch out for

Negative numbers: If the problem involves sums, and the array contains negative numbers, the window might become valid again by expanding. This breaks the monotonicity required for a classic sliding window! You might need Prefix Sums + a Hash Map instead.
Updating the best result: Be careful when you update your best result. Usually, you update it right after the while loop (when the window is guaranteed to be valid).