Arrays, Strings & Sliding Window

TL;DR

• Two Pointers: Solve sorted array / palindrome / pair sum problems in O(n).
• Sliding Window: Maximum/minimum in a subarray, longest substring without repeats.
• Prefix Sum: Range sum queries in O(1) after O(n) preprocessing.
• Hash Maps: Turn O(n²) brute force into O(n) by trading space for time.

Step 1: Two Pointers

Two pointers emerged because brute-forcing pairs in an array means nested loops — O(n²). Engineers realized that if the data is sorted (or you can sort it), you only need one pass with a pointer at each end, collapsing O(n²) to O(n). You'll reach for this anytime you're matching pairs, checking palindromes, partitioning arrays, or merging sorted data. In interviews it appears in roughly 30% of array problems — it's one of the first techniques you should try when you see a sorted array or need to find a pair meeting some condition.

Pattern: Start/End Pointers

// Two Sum (sorted array) — O(n)
function twoSum(nums: number[], target: number): [number, number] {
  let left = 0;
  let right = nums.length - 1;

  while (left < right) {
    const sum = nums[left] + nums[right];
    if (sum === target) return [left, right];
    if (sum < target) left++;   // Need bigger sum → move left pointer right
    else right--;               // Need smaller sum → move right pointer left
  }

  return [-1, -1]; // Not found
}

Pattern: Palindrome Check

function isPalindrome(s: string): boolean {
  let left = 0;
  let right = s.length - 1;

  while (left < right) {
    if (s[left] !== s[right]) return false;
    left++;
    right--;
  }
  return true;
}

Pattern: Remove Duplicates (In-Place)

// Remove duplicates from sorted array — O(n) time, O(1) space
function removeDuplicates(nums: number[]): number {
  if (nums.length === 0) return 0;

  let writePointer = 1; // Where to write next unique value

  for (let readPointer = 1; readPointer < nums.length; readPointer++) {
    if (nums[readPointer] !== nums[readPointer - 1]) {
      nums[writePointer] = nums[readPointer];
      writePointer++;
    }
  }

  return writePointer; // New length
}

Pattern: Container With Most Water

function maxArea(height: number[]): number {
  let left = 0, right = height.length - 1;
  let maxWater = 0;

  while (left < right) {
    const width = right - left;
    const h = Math.min(height[left], height[right]);
    maxWater = Math.max(maxWater, width * h);

    // Move the shorter side inward (can only improve by making height bigger)
    if (height[left] < height[right]) left++;
    else right--;
  }

  return maxWater;
}

Step 2: Sliding Window

Sliding window was born from a simple observation: if you're computing something over every contiguous subarray (like max sum of k elements), you don't need to recompute from scratch each time — just slide the window by adding the new element and dropping the old one. This turns O(n×k) brute force into O(n). You'll use this for any problem that says "contiguous subarray", "longest substring", or "window of size k". Variable-size windows handle problems like "shortest subarray with sum ≥ target" or "longest substring with at most k distinct characters".

Fixed-Size Window

// Maximum sum of subarray of size k
function maxSumSubarray(nums: number[], k: number): number {
  // Calculate first window
  let windowSum = 0;
  for (let i = 0; i < k; i++) {
    windowSum += nums[i];
  }

  let maxSum = windowSum;

  // Slide: add new element, remove old element
  for (let i = k; i < nums.length; i++) {
    windowSum += nums[i];      // Add new element entering window
    windowSum -= nums[i - k];  // Remove element leaving window
    maxSum = Math.max(maxSum, windowSum);
  }

  return maxSum;
}

Variable-Size Window (Expand/Shrink)

// Longest substring without repeating characters — O(n)
function lengthOfLongestSubstring(s: string): number {
  const seen = new Map<string, number>(); // char → last index
  let maxLen = 0;
  let left = 0;

  for (let right = 0; right < s.length; right++) {
    const char = s[right];

    // If char already in window, shrink from left
    if (seen.has(char) && seen.get(char)! >= left) {
      left = seen.get(char)! + 1; // Move past the duplicate
    }

    seen.set(char, right);
    maxLen = Math.max(maxLen, right - left + 1);
  }

  return maxLen;
}
// "abcabcbb" → 3 ("abc")
// "bbbbb" → 1 ("b")

Minimum Window Substring

// Find smallest substring of s that contains all chars of t
function minWindow(s: string, t: string): string {
  const need = new Map<string, number>();
  for (const c of t) need.set(c, (need.get(c) || 0) + 1);

  let have = 0, required = need.size;
  let left = 0;
  let result = '';
  let minLen = Infinity;
  const window = new Map<string, number>();

  for (let right = 0; right < s.length; right++) {
    const char = s[right];
    window.set(char, (window.get(char) || 0) + 1);

    // Check if current char satisfies a requirement
    if (need.has(char) && window.get(char) === need.get(char)) {
      have++;
    }

    // Shrink window while all requirements met
    while (have === required) {
      if (right - left + 1 < minLen) {
        minLen = right - left + 1;
        result = s.slice(left, right + 1);
      }

      const leftChar = s[left];
      window.set(leftChar, window.get(leftChar)! - 1);
      if (need.has(leftChar) && window.get(leftChar)! < need.get(leftChar)!) {
        have--;
      }
      left++;
    }
  }

  return result;
}

Step 3: Hash Map Patterns

Hash maps exist because the fundamental computer science question "does this value exist in my collection?" takes O(n) with arrays but O(1) with hash-based lookup. Every time you catch yourself writing a nested loop to check membership or find a complement, a hash map can collapse it to a single pass. This is the single most impactful optimization technique in coding interviews — it transforms brute-force O(n²) solutions into elegant O(n) ones by trading space for time. You'll use it for frequency counting, grouping, deduplication, and two-sum-style complement problems.

// Two Sum (unsorted) — O(n) with hash map
function twoSum(nums: number[], target: number): [number, number] {
  const map = new Map<number, number>(); // value → index

  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i];
    if (map.has(complement)) {
      return [map.get(complement)!, i];
    }
    map.set(nums[i], i);
  }

  return [-1, -1];
}

// Group Anagrams — O(n * k log k)
function groupAnagrams(strs: string[]): string[][] {
  const map = new Map<string, string[]>();

  for (const str of strs) {
    const key = str.split('').sort().join(''); // Sort chars as key
    if (!map.has(key)) map.set(key, []);
    map.get(key)!.push(str);
  }

  return Array.from(map.values());
}
// ["eat","tea","tan","ate","nat","bat"]
// → [["eat","tea","ate"], ["tan","nat"], ["bat"]]

// Frequency Counter Pattern
function topKFrequent(nums: number[], k: number): number[] {
  const freq = new Map<number, number>();
  for (const n of nums) freq.set(n, (freq.get(n) || 0) + 1);

  return [...freq.entries()]
    .sort((a, b) => b[1] - a[1])
    .slice(0, k)
    .map(([num]) => num);
}

Step 4: Prefix Sum

Prefix sum was invented because repeatedly calculating the sum of a range in an array is expensive — O(n) per query, O(n×q) for q queries. By precomputing cumulative sums in O(n), every subsequent range query becomes O(1) subtraction. It's the go-to technique when you need repeated range computations: sum between indices, counting elements in a range, or the classic "number of subarrays that sum to k". In production, it shows up in analytics dashboards, time-series data, and image processing (integral images).

// Range sum queries in O(1) after O(n) build
class PrefixSum {
  private prefix: number[];

  constructor(nums: number[]) {
    this.prefix = new Array(nums.length + 1).fill(0);
    for (let i = 0; i < nums.length; i++) {
      this.prefix[i + 1] = this.prefix[i] + nums[i];
    }
  }

  // Sum of nums[left..right] inclusive
  rangeSum(left: number, right: number): number {
    return this.prefix[right + 1] - this.prefix[left];
  }
}

// Usage
const ps = new PrefixSum([1, 2, 3, 4, 5]);
ps.rangeSum(1, 3); // 2 + 3 + 4 = 9

// Subarray Sum Equals K — O(n) with prefix sum + hash map
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;
    // If (sum - k) exists as a previous prefix sum, we found a subarray
    if (prefixCount.has(sum - k)) {
      count += prefixCount.get(sum - k)!;
    }
    prefixCount.set(sum, (prefixCount.get(sum) || 0) + 1);
  }

  return count;
}

Step 5: Binary Search

Binary search is one of the oldest algorithms in computing (published 1946, first bug-free version 1962). It exploits sorted order to eliminate half the search space with each comparison, giving O(log n) — searching 1 billion items in just 30 steps. Beyond finding a target in a sorted array, it applies anywhere you have a monotonic condition: "find the first/last value where X is true", minimum speed problems, capacity allocation, and even answer-space searching where you binary-search the result itself.

// Classic binary search — O(log n)
function binarySearch(nums: number[], target: number): number {
  let left = 0, right = nums.length - 1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (nums[mid] === target) return mid;
    if (nums[mid] < target) left = mid + 1;
    else right = mid - 1;
  }

  return -1; // Not found
}

// Find first position (lower bound)
function lowerBound(nums: number[], target: number): number {
  let left = 0, right = nums.length;

  while (left < right) {
    const mid = Math.floor((left + right) / 2);
    if (nums[mid] < target) left = mid + 1;
    else right = mid;
  }

  return left; // First index where nums[i] >= target
}

// Search in rotated sorted array
function searchRotated(nums: number[], target: number): number {
  let left = 0, right = nums.length - 1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (nums[mid] === target) return mid;

    // Left half is sorted
    if (nums[left] <= nums[mid]) {
      if (target >= nums[left] && target < nums[mid]) {
        right = mid - 1; // Target in sorted left half
      } else {
        left = mid + 1;
      }
    }
    // Right half is sorted
    else {
      if (target > nums[mid] && target <= nums[right]) {
        left = mid + 1; // Target in sorted right half
      } else {
        right = mid - 1;
      }
    }
  }

  return -1;
}

Step 6: Stack Patterns

Stacks became fundamental because many problems have a "last-in, first-out" nature — matching brackets, undo operations, function call tracking. The monotonic stack variant was discovered for problems like "next greater element" and "largest rectangle in histogram" where you need to efficiently track the nearest larger/smaller values. Without it, these problems require O(n²) comparisons; with a monotonic stack, you achieve O(n) because each element is pushed and popped at most once.

// Valid Parentheses — O(n)
function isValid(s: string): boolean {
  const stack: string[] = [];
  const map: Record<string, string> = { ')': '(', ']': '[', '}': '{' };

  for (const char of s) {
    if (char in map) {
      if (stack.pop() !== map[char]) return false;
    } else {
      stack.push(char);
    }
  }

  return stack.length === 0;
}

// Monotonic Stack: Next Greater Element
function nextGreaterElement(nums: number[]): number[] {
  const result = new Array(nums.length).fill(-1);
  const stack: number[] = []; // Stack of indices

  for (let i = 0; i < nums.length; i++) {
    // Pop elements smaller than current (they found their next greater)
    while (stack.length && nums[stack[stack.length - 1]] < nums[i]) {
      const idx = stack.pop()!;
      result[idx] = nums[i];
    }
    stack.push(i);
  }

  return result;
}
// [2, 1, 2, 4, 3] → [4, 2, 4, -1, -1]

Pattern Recognition Cheat Sheet

Interview Questions

1. How do you identify a sliding window problem?

   • Keywords: "contiguous subarray", "longest/shortest substring", "at most k", "window of size k". You need to find an optimal contiguous segment. Fixed window = exact size. Variable = expand right, shrink left when constraint violated.

2. Two Pointers vs Sliding Window?

   • Two Pointers: work inward from both ends (sorted arrays, palindromes). Sliding Window: both pointers move right, left shrinks when needed (subarray/substring problems).

3. When to use a Hash Map in DSA?

   • Whenever you need O(1) lookup. Converting "does this value exist?" from O(n) scan to O(1). Counting frequencies. Mapping values to indices. Caching computed results.

4. What's the time complexity of sliding window?

   • O(n). Even though it looks like nested loops, each element is added and removed from the window at most once. Both pointers only move forward.