Algorithm Techniques: Sliding Window

What is the sliding window technique?

The sliding window is an algorithm method that iterates a range, or "window" through a sequential data structure. This is an efficient way to process elements using only one loop.

When is this technique useful?

As an alternative to nested loops, the sliding window can reduce the time complexity from O(n^2) to O(n). It is useful when solving problems that require finding a subrange or subsequence. For example, when finding a subarray with the highest sum or the longest substring without repeating characters.

Common problems this technique solves:

• Finding the longest substring without repeating characters

// typescript solution:

function lengthOfLongestSubstring(s: string): number {
    let max = 0;
    let start = 0;
    const map = new Map();
    for (let i = 0; i < s.length; i++) {
        if (map.has(s[i])) {
            start = Math.max(map.get(s[i]) + 1, start);
        }
        map.set(s[i], i);
        max = Math.max(max, i - start + 1);
    }
    return max;
};

• Finding the smallest subarray with a minimum sum

// typescript solution: 

function minSubArrayLen(target: number, nums: number[]): number {
  let minLength = Infinity;
  let left = 0, right = 0, sum = 0;

  while (right < nums.length) {
    sum += nums[right];

    while (sum >= target) {
        minLength = Math.min(minLength, right - left + 1);
        if (minLength === 1) return minLength; 
        sum -= nums[left];
        left++;
    }
    right++;
  }

  return minLength === Infinity ? 0 : minLength;
}