Data Structures and Algorithms Interview Guide 2026: LeetCode Patterns That Actually Work

1.  Two Pointers          — Pair sum, palindrome, containers
2.  Sliding Window        — Subarray problems with constraints
3.  Fast & Slow Pointers  — Cycle detection, middle of list
4.  Binary Search         — Any sorted/rotated array
5.  Merge Intervals       — Overlapping interval problems
6.  Cyclic Sort           — Array with range 1-N values
7.  Tree BFS              — Level-order, shortest path in tree
8.  Tree DFS              — Path problems, subtree matching
9.  Two Heaps             — Median, scheduling
10. Subsets               — Combinations, permutations
11. Modified Binary Search — Find element in rotated array
12. Top K Elements        — K largest, frequent elements
13. K-way Merge           — Merge K sorted lists
14. Dynamic Programming   — Optimization, counting paths

// Two Sum in sorted array — O(n) time, O(1) space
function twoSum(nums: number[], target: 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++
    else right--
  }
  return []
}

// Container with Most Water
function maxArea(height: number[]): number {
  let left = 0, right = height.length - 1
  let maxWater = 0

  while (left < right) {
    const water = Math.min(height[left], height[right]) * (right - left)
    maxWater = Math.max(maxWater, water)
    // Move the shorter side inward
    if (height[left] < height[right]) left++
    else right--
  }
  return maxWater
}

// 3Sum — O(n²) time
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 left = i + 1, right = nums.length - 1
    while (left < right) {
      const sum = nums[i] + nums[left] + nums[right]
      if (sum === 0) {
        result.push([nums[i], nums[left], nums[right]])
        while (left < right && nums[left] === nums[left + 1]) left++
        while (left < right && nums[right] === nums[right - 1]) right--
        left++; right--
      } else if (sum < 0) left++
      else right--
    }
  }
  return result
}

// Longest substring without repeating characters
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]
    // Shrink window if char seen inside current window
    if (seen.has(char) && seen.get(char)! >= left) {
      left = seen.get(char)! + 1
    }
    seen.set(char, right)
    maxLen = Math.max(maxLen, right - left + 1)
  }
  return maxLen
}

// Minimum window substring (hard)
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 minLen = Infinity, minLeft = 0

  const window = new Map<string, number>()

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

    if (need.has(c) && window.get(c) === need.get(c)) have++

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

  return minLen === Infinity ? '' : s.slice(minLeft, minLeft + minLen)
}

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

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

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

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

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

// Find minimum in rotated sorted array
function findMin(nums: number[]): number {
  let left = 0, right = nums.length - 1

  while (left < right) {
    const mid = left + Math.floor((right - left) / 2)
    if (nums[mid] > nums[right]) left = mid + 1  // Min is in right half
    else right = mid  // Min is in left half (including mid)
  }
  return nums[left]
}

// DFS: all paths root to leaf
function allPaths(root: TreeNode | null): number[][] {
  const paths: number[][] = []

  function dfs(node: TreeNode | null, path: number[]) {
    if (!node) return
    path.push(node.val)

    if (!node.left && !node.right) {
      paths.push([...path])
    }
    dfs(node.left, path)
    dfs(node.right, path)
    path.pop()  // Backtrack
  }

  dfs(root, [])
  return paths
}

// BFS: level order traversal
function levelOrder(root: TreeNode | null): number[][] {
  if (!root) return []
  const result: number[][] = []
  const queue = [root]

  while (queue.length) {
    const levelSize = queue.length
    const level: number[] = []

    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift()!
      level.push(node.val)
      if (node.left) queue.push(node.left)
      if (node.right) queue.push(node.right)
    }
    result.push(level)
  }
  return result
}

// LCA — Lowest Common Ancestor
function lowestCommonAncestor(
  root: TreeNode | null,
  p: TreeNode,
  q: TreeNode
): TreeNode | null {
  if (!root || root === p || root === q) return root

  const left = lowestCommonAncestor(root.left, p, q)
  const right = lowestCommonAncestor(root.right, p, q)

  if (left && right) return root  // p and q on different sides
  return left ?? right
}

// BFS for shortest path
function shortestPath(grid: number[][], start: [number, number], end: [number, number]): number {
  const [rows, cols] = [grid.length, grid[0].length]
  const dirs = [[0,1],[0,-1],[1,0],[-1,0]]
  const visited = new Set<string>()
  const queue: [[number, number], number][] = [[start, 0]]

  visited.add(start.toString())

  while (queue.length) {
    const [[row, col], dist] = queue.shift()!
    if (row === end[0] && col === end[1]) return dist

    for (const [dr, dc] of dirs) {
      const [nr, nc] = [row + dr, col + dc]
      const key = `${nr},${nc}`
      if (nr >= 0 && nr < rows && nc >= 0 && nc < cols
          && grid[nr][nc] === 0 && !visited.has(key)) {
        visited.add(key)
        queue.push([[nr, nc], dist + 1])
      }
    }
  }
  return -1
}

// DFS to count islands
function numIslands(grid: string[][]): number {
  let count = 0

  function dfs(row: number, col: number) {
    if (row < 0 || row >= grid.length || col < 0 || col >= grid[0].length
        || grid[row][col] !== '1') return

    grid[row][col] = '0'  // Mark visited
    dfs(row + 1, col); dfs(row - 1, col)
    dfs(row, col + 1); dfs(row, col - 1)
  }

  for (let r = 0; r < grid.length; r++) {
    for (let c = 0; c < grid[0].length; c++) {
      if (grid[r][c] === '1') {
        count++
        dfs(r, c)
      }
    }
  }
  return count
}

DP = Recursion + Memoization (top-down) OR Tabulation (bottom-up)
When to use: optimization (min/max), counting (how many ways), feasibility (can/cannot)

Steps:
1. Define state: what does dp[i] represent?
2. Base case: dp[0] or dp[1]
3. Recurrence: dp[i] in terms of previous states
4. Result: usually dp[n] or max(dp)

// Climb stairs (Fibonacci)
function climbStairs(n: number): number {
  if (n <= 2) return n
  let [prev, curr] = [1, 2]
  for (let i = 3; i <= n; i++) {
    [prev, curr] = [curr, prev + curr]
  }
  return curr
}

// 0/1 Knapsack
function knapsack(weights: number[], values: number[], capacity: number): number {
  const n = weights.length
  const dp = Array(n + 1).fill(null).map(() => Array(capacity + 1).fill(0))

  for (let i = 1; i <= n; i++) {
    for (let w = 0; w <= capacity; w++) {
      dp[i][w] = dp[i-1][w]  // Don't take item i
      if (weights[i-1] <= w) {
        dp[i][w] = Math.max(dp[i][w], dp[i-1][w - weights[i-1]] + values[i-1])
      }
    }
  }
  return dp[n][capacity]
}

// Longest Common Subsequence
function lcs(s1: string, s2: string): number {
  const m = s1.length, n = s2.length
  const dp = Array(m + 1).fill(null).map(() => Array(n + 1).fill(0))

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (s1[i-1] === s2[j-1]) dp[i][j] = dp[i-1][j-1] + 1
      else dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1])
    }
  }
  return dp[m][n]
}

// Coin change (fewest coins)
function coinChange(coins: number[], amount: number): number {
  const dp = Array(amount + 1).fill(Infinity)
  dp[0] = 0

  for (let i = 1; i <= amount; i++) {
    for (const coin of coins) {
      if (coin <= i) dp[i] = Math.min(dp[i], dp[i - coin] + 1)
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount]
}

Days 1-30: Foundations
  - Arrays & Strings: Two pointers, sliding window
  - Linked Lists: Reversal, cycle detection
  - Stacks & Queues: Monotonic stack, BFS
  - Binary Search
  LeetCode target: 50 problems (easy/medium mix)

Days 31-60: Core Patterns
  - Trees: DFS, BFS, LCA, diameter
  - Graphs: BFS, DFS, topological sort, union-find
  - Dynamic Programming: 1D, 2D, interval
  LeetCode target: 80 more problems (mostly medium)

Days 61-90: Hard Problems + Mock Interviews
  - Hard DP: edit distance, burst balloons
  - Graph algorithms: Dijkstra, Bellman-Ford
  - Advanced: tries, segment trees, heap tricks
  - Mock interviews: 3x per week (Pramp, Interviewing.io)
  LeetCode target: 40 more problems (medium/hard)

Must-solve problems (in order):
Arrays: Two Sum, Best Time to Buy Stock, Product Except Self
Strings: Longest Substring, Group Anagrams, Valid Parentheses
Trees: Invert Tree, Max Depth, LCA, Serialize/Deserialize
Graphs: Number of Islands, Course Schedule, Word Ladder
DP: Climb Stairs, House Robber, Longest Increasing Subsequence
Intervals: Merge Intervals, Non-overlapping Intervals