16 — Sliding Window & Two Pointers

Sliding Window — Fixed Size

Window of exactly size k.

// Maximum sum subarray of size k
function maxSumSubarray(nums: number[], k: number): number {
  let windowSum = 0, maxSum = -Infinity;
  
  for (let i = 0; i < nums.length; i++) {
    windowSum += nums[i];
    if (i >= k) windowSum -= nums[i - k]; // Shrink from left
    if (i >= k - 1) maxSum = Math.max(maxSum, windowSum);
  }
  return maxSum;
}

---

Sliding Window — Variable Size

Expand right, shrink left when constraint violated.

// Longest substring without repeating characters
function lengthOfLongestSubstring(s: string): number {
  const seen = new Map<string, number>(); // char → last index
  let maxLen = 0, left = 0;
  
  for (let right = 0; right < s.length; right++) {
    if (seen.has(s[right]) && seen.get(s[right])! >= left) {
      left = seen.get(s[right])! + 1;
    }
    seen.set(s[right], right);
    maxLen = Math.max(maxLen, right - left + 1);
  }
  return maxLen;
}

Minimum Window Substring

function minWindow(s: string, t: string): string {
  const need = new Map<string, number>();
  for (const ch of t) need.set(ch, (need.get(ch) ?? 0) + 1);
  
  let have = 0, required = need.size;
  let left = 0, minLen = Infinity, minStart = 0;
  const window = new Map<string, number>();
  
  for (let right = 0; right < s.length; right++) {
    const ch = s[right];
    window.set(ch, (window.get(ch) ?? 0) + 1);
    if (need.has(ch) && window.get(ch) === need.get(ch)) have++;
    
    while (have === required) {
      if (right - left + 1 < minLen) {
        minLen = right - left + 1;
        minStart = left;
      }
      const leftCh = s[left];
      window.set(leftCh, window.get(leftCh)! - 1);
      if (need.has(leftCh) && window.get(leftCh)! < need.get(leftCh)!) have--;
      left++;
    }
  }
  return minLen === Infinity ? '' : s.substring(minStart, minStart + minLen);
}

---

Two Pointers

Two Sum (Sorted Array)

function twoSum(nums: number[], target: number): [number, number] {
  let lo = 0, hi = nums.length - 1;
  while (lo < hi) {
    const sum = nums[lo] + nums[hi];
    if (sum === target) return [lo, hi];
    if (sum < target) lo++;
    else hi--;
  }
  return [-1, -1];
}

Three Sum

function threeSum(nums: number[]): number[][] {
  nums.sort((a, b) => a - b);
  const result: number[][] = [];
  
  for (let i = 0; i < nums.length - 2; i++) {
    if (i > 0 && nums[i] === nums[i - 1]) continue; // Skip duplicates
    let lo = i + 1, hi = nums.length - 1;
    
    while (lo < hi) {
      const sum = nums[i] + nums[lo] + nums[hi];
      if (sum === 0) {
        result.push([nums[i], nums[lo], nums[hi]]);
        while (lo < hi && nums[lo] === nums[lo + 1]) lo++;
        while (lo < hi && nums[hi] === nums[hi - 1]) hi--;
        lo++; hi--;
      } else if (sum < 0) lo++;
      else hi--;
    }
  }
  return result;
}

Container With Most Water

function maxArea(height: number[]): number {
  let lo = 0, hi = height.length - 1, max = 0;
  while (lo < hi) {
    max = Math.max(max, Math.min(height[lo], height[hi]) * (hi - lo));
    if (height[lo] < height[hi]) lo++;
    else hi--;
  }
  return max;
}

---

Subarray Problems

Maximum Subarray Sum (Kadane's)

function maxSubArray(nums: number[]): number {
  let current = nums[0], max = nums[0];
  for (let i = 1; i < nums.length; i++) {
    current = Math.max(nums[i], current + nums[i]);
    max = Math.max(max, current);
  }
  return max;
}

Count Subarrays with Sum = K

function subarraySum(nums: number[], k: number): number {
  const prefixCount = new Map<number, number>([[0, 1]]);
  let sum = 0, count = 0;
  
  for (const num of nums) {
    sum += num;
    count += prefixCount.get(sum - k) ?? 0;
    prefixCount.set(sum, (prefixCount.get(sum) ?? 0) + 1);
  }
  return count;
}

---

Pattern Summary

---

Key Takeaways

• Fixed window: maintain sum/count, slide by adding right and removing left
• Variable window: expand right always, shrink left only when constraint breaks
• Two pointers: sorted arrays → converge from both ends
• Prefix sum + hashmap: O(n) for subarray sum problems — not a sliding window
• Sliding window is O(n) — each element enters and leaves window at most once