📅 Day 4: Array Patterns – Two Pointers and Sliding Window

🧠 Concept Deep Dive

Many array problems involve finding subarrays, pairs, or patterns that follow a rule. Instead of using brute-force nested loops (which are slow), we use optimized pointer techniques.

✌️ Two Pointers

Two variables (pointers) scan the array from different directions or at different speeds. Ideal for sorted arrays or problems with conditions between pairs.

🚪 Sliding Window

A window (subarray) moves through the array, adjusting its size dynamically to meet certain criteria. Best for tracking sums, averages, or unique elements.

🧭 When to Use

✌️ Two Pointers Example: Pair Sum

🧩 Problem:

Given a sorted array and a target, find if any two numbers sum to the target.

🔍 TypeScript Code

function hasPairWithSum(arr: number[], target: number): boolean {
  let left = 0;
  let right = arr.length - 1;

  while (left < right) {
    const sum = arr[left] + arr[right];

    if (sum === target) return true;
    if (sum < target) left++;
    else right--;
  }
  return false;
}

// Test
console.log(hasPairWithSum([1, 2, 4, 7, 11, 15], 15)); // Output: true

🧠 Why It Works

• The array is sorted.
• Increasing left increases the sum, decreasing right decreases the sum.

🚪 Sliding Window Example: Max Sum of Subarray of Size K

🧩 Problem:

Given an array of numbers and a number k, find the maximum sum of any contiguous subarray of size k.

🔍 TypeScript Code

function maxSubarraySum(arr: number[], k: number): number {
  let maxSum = 0;
  let windowSum = 0;

  for (let i = 0; i < k; i++) {
    windowSum += arr[i];
  }
  maxSum = windowSum;

  for (let i = k; i < arr.length; i++) {
    windowSum += arr[i] - arr[i - k];
    maxSum = Math.max(maxSum, windowSum);
  }
  return maxSum;
}

// Test
console.log(maxSubarraySum([2, 1, 5, 1, 3, 2], 3)); // Output: 9

🧠 Why It Works

• First calculate the sum of the first window of size k.
• Then, slide the window one index at a time by adding the next element and removing the first element of the previous window.

🧠 Visual Representation

Array:       [1, 2, 3, 4, 5, 6]
Window (k=3):      → [1,2,3] → [2,3,4] → [3,4,5] → [4,5,6]
Two Pointers:   ↑           ↑
              left        right

🛠 Real-world Application

🔧 Sliding Window:

• Streaming temperature sensors: track rolling averages over 10 seconds.
• Data packets: max throughput over fixed-size timeframes.

🔧 Two Pointers:

• Detecting fraud: find if any two transactions sum to a suspicious amount.
• Video processing: comparing frames forward/backward.

🧪 Example Practice: Longest Substring with K Unique Characters

Problem

Find the length of the longest substring with at most k distinct characters.

Code

function longestKSubstr(s: string, k: number): number {
  let start = 0;
  let maxLength = 0;
  const charMap = new Map<string, number>();

  for (let end = 0; end < s.length; end++) {
    const endChar = s[end];
    charMap.set(endChar, (charMap.get(endChar) || 0) + 1);

    while (charMap.size > k) {
      const startChar = s[start];
      charMap.set(startChar, charMap.get(startChar)! - 1);
      if (charMap.get(startChar) === 0) charMap.delete(startChar);
      start++;
    }
    maxLength = Math.max(maxLength, end - start + 1);
  }

  return maxLength;
}

// Test
console.log(longestKSubstr("eceba", 2)); // Output: 3 ("ece")

🧠 Big O Recap

🏠 Homework (LeetCode-style)

Problem: Minimum Size Subarray Sum

Given an array of positive integers nums and a positive integer target, return the minimal length of a subarray of which the sum is greater than or equal to target. If there is no such subarray, return 0.

Function Signature:

function minSubArrayLen(target: number, nums: number[]): number;

Example 1

Input: target = 7, nums = [2,3,1,2,4,3]
Output: 2 // [4,3]

Example 2

Input: target = 15, nums = [1,2,3,4,5]
Output: 5 // entire array

🔍 Hint: Use sliding window and adjust window size until sum ≥ target

🧾 Summary

• Two Pointers = simple but powerful way to reduce nested loops.
• Sliding Window = excellent for contiguous subarray/string problems.
• Know the difference: Two Pointers often compares ends, while Sliding Window grows/shrinks a range.

🔜 Coming Up

📅 Day 4: Strings – Manipulation and Common Techniques

We'll explore string traversal, building, comparing, and efficient pattern checks like palindromes, anagrams, and reversals.