Algorithm Patterns

1. Why Patterns Matter

LeetCode is not about memorizing 500 solutions. If you memorize solutions, you will blank the moment a problem changes even one detail. The real skill is recognizing patterns and knowing which technique applies to which type of problem.

• There are roughly 15 core patterns that cover the vast majority of interview problems.
• Once you learn a pattern, every problem that uses it becomes a variation -- not a brand new puzzle.
• Patterns give you a starting framework so you are never staring at a blank screen.
• Interviewers do not expect novel algorithms -- they expect you to recognize and apply known techniques.

2. Two Pointers

Use two pointers to scan a data structure (usually an array) from different positions. This often reduces an O(n^2) brute force to O(n).

Two main types:

• Converging pointers -- one at the start, one at the end, moving toward each other.
• Same direction pointers -- both start at the beginning; one moves fast, one moves slow.

Converging Two Pointers

Two Sum II (Sorted Array) -- Given a sorted array and a target, find two numbers that add up to the target.

Python
def two_sum(numbers, target):
    left, right = 0, len(numbers) - 1
    while left < right:
        curr_sum = numbers[left] + numbers[right]
        if curr_sum == target:
            return [left + 1, right + 1]  # 1-indexed
        elif curr_sum < target:
            left += 1    # need bigger sum
        else:
            right -= 1   # need smaller sum

JavaScript
function twoSum(numbers, target) {
    let left = 0, right = numbers.length - 1;
    while (left < right) {
        const sum = numbers[left] + numbers[right];
        if (sum === target) return [left + 1, right + 1];
        else if (sum < target) left++;
        else right--;
    }
}

Container With Most Water -- Given height array, find two lines that form the container holding the most water.

Python
def max_area(height):
    left, right = 0, len(height) - 1
    best = 0
    while left < right:
        width = right - left
        h = min(height[left], height[right])
        best = max(best, width * h)
        # Move the shorter side -- it's the bottleneck
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1
    return best

JavaScript
function maxArea(height) {
    let left = 0, right = height.length - 1, best = 0;
    while (left < right) {
        const w = right - left;
        const h = Math.min(height[left], height[right]);
        best = Math.max(best, w * h);
        if (height[left] < height[right]) left++;
        else right--;
    }
    return best;
}

3Sum -- Find all unique triplets that sum to zero. Sort the array, fix one number, then use converging two pointers on the remainder. Skip duplicates to avoid repeats. Time O(n^2), Space O(1) extra.

Same Direction (Fast / Slow)

Remove Duplicates from Sorted Array -- Keep a slow pointer at the position to write, fast pointer scans ahead. When fast finds a new value, write it at slow and advance slow.

Move Zeroes -- Same idea: slow pointer tracks the next position for a nonzero value. Fast pointer scans the array. Swap nonzero values to the front.

Two Pointers Templates

Python
# Template: Converging Two Pointers
def converging(arr, target):
    left, right = 0, len(arr) - 1
    while left < right:
        # compute current value from arr[left], arr[right]
        if condition_met:
            return result
        elif need_larger:
            left += 1
        else:
            right -= 1

# Template: Same Direction (partition / remove)
def same_direction(arr):
    slow = 0
    for fast in range(len(arr)):
        if arr[fast] meets_condition:
            arr[slow] = arr[fast]
            slow += 1
    return slow  # new length

JavaScript
// Template: Converging Two Pointers
function converging(arr, target) {
    let left = 0, right = arr.length - 1;
    while (left < right) {
        // compute current value from arr[left], arr[right]
        if (conditionMet) return result;
        else if (needLarger) left++;
        else right--;
    }
}

// Template: Same Direction (partition / remove)
function sameDirection(arr) {
    let slow = 0;
    for (let fast = 0; fast < arr.length; fast++) {
        if (arr[fast] meets condition) {
            arr[slow] = arr[fast];
            slow++;
        }
    }
    return slow;
}

3. Sliding Window

Maintain a "window" over a contiguous subarray or substring and slide it across the input. This avoids recomputing from scratch each time -- you add the new element and remove the old one.

Two types:

• Fixed size window -- window size k is given. Slide it one position at a time.
• Variable size window -- expand until condition breaks, then shrink from the left.

Fixed Size Window

Maximum Sum Subarray of Size K

Python
def max_sum_subarray(arr, k):
    window_sum = sum(arr[:k])
    best = window_sum
    for i in range(k, len(arr)):
        window_sum += arr[i] - arr[i - k]  # slide: add right, remove left
        best = max(best, window_sum)
    return best

JavaScript
function maxSumSubarray(arr, k) {
    let windowSum = 0;
    for (let i = 0; i < k; i++) windowSum += arr[i];
    let best = windowSum;
    for (let i = k; i < arr.length; i++) {
        windowSum += arr[i] - arr[i - k];
        best = Math.max(best, windowSum);
    }
    return best;
}

Variable Size Window

Minimum Size Subarray Sum -- Find the smallest subarray whose sum is at least the target. Expand right to grow the window, shrink left when the sum is big enough.

Longest Substring Without Repeating Characters -- Classic variable window problem. Expand right, if duplicate found, shrink left until valid again.

Python
def length_of_longest_substring(s):
    seen = {}  # char -> most recent index
    left = 0
    best = 0
    for right in range(len(s)):
        if s[right] in seen and seen[s[right]] >= left:
            left = seen[s[right]] + 1  # shrink past the duplicate
        seen[s[right]] = right
        best = max(best, right - left + 1)
    return best

JavaScript
function lengthOfLongestSubstring(s) {
    const seen = new Map();
    let left = 0, best = 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);
        best = Math.max(best, right - left + 1);
    }
    return best;
}

Sliding Window Templates

Python
# Template: Fixed Size Window
def fixed_window(arr, k):
    # Initialize window with first k elements
    window = compute(arr[0:k])
    best = window
    for i in range(k, len(arr)):
        window = window + arr[i] - arr[i - k]  # add new, remove old
        best = update(best, window)
    return best

# Template: Variable Size Window
def variable_window(arr):
    left = 0
    best = 0
    state = {}  # track window contents
    for right in range(len(arr)):
        # Expand: add arr[right] to state
        while window_is_invalid(state):
            # Shrink: remove arr[left] from state
            left += 1
        best = max(best, right - left + 1)
    return best

JavaScript
// Template: Fixed Size Window
function fixedWindow(arr, k) {
    let window = 0;
    for (let i = 0; i < k; i++) window += arr[i];
    let best = window;
    for (let i = k; i < arr.length; i++) {
        window += arr[i] - arr[i - k];
        best = Math.max(best, window);
    }
    return best;
}

// Template: Variable Size Window
function variableWindow(arr) {
    let left = 0, best = 0;
    const state = new Map();
    for (let right = 0; right < arr.length; right++) {
        // Expand: add arr[right] to state
        while (windowIsInvalid(state)) {
            // Shrink: remove arr[left] from state
            left++;
        }
        best = Math.max(best, right - left + 1);
    }
    return best;
}

4. Binary Search Pattern

Binary search is not just for finding an element in a sorted array. The deeper insight is: any time you can halve a search space, you can binary search. This includes searching on the answer itself.

Standard Binary Search Template

Python
def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = left + (right - left) // 2  # avoids overflow
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1  # not found

JavaScript
function binarySearch(arr, target) {
    let left = 0, right = arr.length - 1;
    while (left <= right) {
        const mid = left + Math.floor((right - left) / 2);
        if (arr[mid] === target) return mid;
        else if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

Binary Search on the Answer

Sometimes you are not searching an array -- you are searching a range of possible answers. If you can write a function canAchieve(x) that returns true/false, and the answers are monotonic (once true, always true), you can binary search on the answer.

Koko Eating Bananas -- Koko has piles of bananas and h hours. Find the minimum eating speed k so she finishes all piles in h hours.

Python
import math

def min_eating_speed(piles, h):
    def can_finish(speed):
        hours = sum(math.ceil(p / speed) for p in piles)
        return hours <= h

    left, right = 1, max(piles)
    while left < right:
        mid = (left + right) // 2
        if can_finish(mid):
            right = mid       # try slower
        else:
            left = mid + 1    # too slow, go faster
    return left

JavaScript
function minEatingSpeed(piles, h) {
    function canFinish(speed) {
        let hours = 0;
        for (const p of piles) hours += Math.ceil(p / speed);
        return hours <= h;
    }

    let left = 1, right = Math.max(...piles);
    while (left < right) {
        const mid = Math.floor((left + right) / 2);
        if (canFinish(mid)) right = mid;
        else left = mid + 1;
    }
    return left;
}

Capacity to Ship Packages Within D Days -- Same idea. Binary search on the ship capacity. The canShip(capacity) function simulates loading packages greedily and checks if it fits in D days.

Binary Search on Answer Template

Python
# Template: Binary Search on the Answer
def search_answer(data):
    def is_feasible(x):
        # return True if x is a valid answer
        pass

    left, right = min_possible, max_possible
    while left < right:
        mid = (left + right) // 2
        if is_feasible(mid):
            right = mid       # try smaller (for minimum)
        else:
            left = mid + 1
    return left

JavaScript
// Template: Binary Search on the Answer
function searchAnswer(data) {
    function isFeasible(x) {
        // return true if x is a valid answer
    }

    let left = minPossible, right = maxPossible;
    while (left < right) {
        const mid = Math.floor((left + right) / 2);
        if (isFeasible(mid)) right = mid;
        else left = mid + 1;
    }
    return left;
}

5. BFS Pattern

Breadth-First Search processes nodes level by level using a queue. It is the go-to for shortest path in unweighted graphs/grids and level-order traversal in trees.

Core BFS Template

Python
from collections import deque

def bfs(graph, start):
    queue = deque([start])
    visited = {start}
    while queue:
        node = queue.popleft()
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

JavaScript
function bfs(graph, start) {
    const queue = [start];
    const visited = new Set([start]);
    while (queue.length > 0) {
        const node = queue.shift();
        for (const neighbor of graph[node]) {
            if (!visited.has(neighbor)) {
                visited.add(neighbor);
                queue.push(neighbor);
            }
        }
    }
}

Multi-Source BFS

Start BFS from multiple sources at once by putting them all in the queue initially. This is key for problems like "distance from nearest X" or "simultaneous spread."

Rotting Oranges -- All rotten oranges spread simultaneously. Find the time for all fresh oranges to rot (or -1 if impossible).

Python
from collections import deque

def oranges_rotting(grid):
    rows, cols = len(grid), len(grid[0])
    queue = deque()
    fresh = 0

    # Collect all rotten oranges as starting points
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 2:
                queue.append((r, c))
            elif grid[r][c] == 1:
                fresh += 1

    minutes = 0
    directions = [(0,1), (0,-1), (1,0), (-1,0)]

    while queue and fresh > 0:
        minutes += 1
        for _ in range(len(queue)):  # process current level
            r, c = queue.popleft()
            for dr, dc in directions:
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
                    grid[nr][nc] = 2
                    fresh -= 1
                    queue.append((nr, nc))

    return minutes if fresh == 0 else -1

JavaScript
function orangesRotting(grid) {
    const rows = grid.length, cols = grid[0].length;
    const queue = [];
    let fresh = 0;

    for (let r = 0; r < rows; r++) {
        for (let c = 0; c < cols; c++) {
            if (grid[r][c] === 2) queue.push([r, c]);
            else if (grid[r][c] === 1) fresh++;
        }
    }

    const dirs = [[0,1],[0,-1],[1,0],[-1,0]];
    let minutes = 0;

    while (queue.length > 0 && fresh > 0) {
        minutes++;
        const size = queue.length;
        for (let i = 0; i < size; i++) {
            const [r, c] = queue.shift();
            for (const [dr, dc] of dirs) {
                const nr = r + dr, nc = c + dc;
                if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] === 1) {
                    grid[nr][nc] = 2;
                    fresh--;
                    queue.push([nr, nc]);
                }
            }
        }
    }
    return fresh === 0 ? minutes : -1;
}

Grid BFS

Number of Islands -- For each unvisited land cell, run BFS to mark the entire island. Count how many times you start a new BFS.

Shortest Path in Grid -- BFS naturally finds the shortest path because it explores all cells at distance d before distance d+1. Track distance by processing one level at a time.

Grid BFS Template

Python
from collections import deque

def grid_bfs(grid, start_r, start_c):
    rows, cols = len(grid), len(grid[0])
    queue = deque([(start_r, start_c, 0)])  # row, col, distance
    visited = {(start_r, start_c)}
    directions = [(0,1), (0,-1), (1,0), (-1,0)]

    while queue:
        r, c, dist = queue.popleft()
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            if (0 <= nr < rows and 0 <= nc < cols
                    and (nr, nc) not in visited
                    and grid[nr][nc] != obstacle):
                visited.add((nr, nc))
                queue.append((nr, nc, dist + 1))

JavaScript
function gridBFS(grid, startR, startC) {
    const rows = grid.length, cols = grid[0].length;
    const queue = [[startR, startC, 0]];
    const visited = new Set([`${startR},${startC}`]);
    const dirs = [[0,1],[0,-1],[1,0],[-1,0]];

    while (queue.length > 0) {
        const [r, c, dist] = queue.shift();
        for (const [dr, dc] of dirs) {
            const nr = r + dr, nc = c + dc;
            const key = `${nr},${nc}`;
            if (nr >= 0 && nr < rows && nc >= 0 && nc < cols
                && !visited.has(key) && grid[nr][nc] !== obstacle) {
                visited.add(key);
                queue.push([nr, nc, dist + 1]);
            }
        }
    }
}

6. DFS & Backtracking

Depth-First Search explores as deep as possible before backtracking. It is the natural choice for tree problems, exploring all paths, and generating combinations/permutations.

Tree DFS

Python
# Recursive DFS Template for Binary Trees
def dfs(node):
    if not node:
        return base_case
    left = dfs(node.left)
    right = dfs(node.right)
    return combine(node.val, left, right)

# Maximum Depth of Binary Tree
def max_depth(root):
    if not root:
        return 0
    return 1 + max(max_depth(root.left), max_depth(root.right))

JavaScript
// Recursive DFS Template for Binary Trees
function dfs(node) {
    if (!node) return baseCase;
    const left = dfs(node.left);
    const right = dfs(node.right);
    return combine(node.val, left, right);
}

// Maximum Depth of Binary Tree
function maxDepth(root) {
    if (!root) return 0;
    return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

Graph DFS

Connected Components -- Run DFS from each unvisited node. Each DFS call discovers one connected component.

Cycle Detection -- In directed graphs, track nodes in the current DFS path. If you visit a node already on the path, there is a cycle. Use three states: unvisited, in-progress, done.

Backtracking

Backtracking is DFS with a twist: you make a choice, recurse, then undo the choice to try the next option. It generates all valid combinations, permutations, or subsets.

Subsets -- Generate all subsets of a set. At each index, choose to include or exclude the element.

Python
def subsets(nums):
    result = []
    def backtrack(start, current):
        result.append(current[:])  # snapshot current state
        for i in range(start, len(nums)):
            current.append(nums[i])       # choose
            backtrack(i + 1, current)      # explore
            current.pop()                  # un-choose
    backtrack(0, [])
    return result

JavaScript
function subsets(nums) {
    const result = [];
    function backtrack(start, current) {
        result.push([...current]);
        for (let i = start; i < nums.length; i++) {
            current.push(nums[i]);         // choose
            backtrack(i + 1, current);     // explore
            current.pop();                  // un-choose
        }
    }
    backtrack(0, []);
    return result;
}

Permutations -- Generate all orderings of the input.

Python
def permute(nums):
    result = []
    def backtrack(current, remaining):
        if not remaining:
            result.append(current[:])
            return
        for i in range(len(remaining)):
            current.append(remaining[i])
            backtrack(current, remaining[:i] + remaining[i+1:])
            current.pop()
    backtrack([], nums)
    return result

JavaScript
function permute(nums) {
    const result = [];
    function backtrack(current, remaining) {
        if (remaining.length === 0) {
            result.push([...current]);
            return;
        }
        for (let i = 0; i < remaining.length; i++) {
            current.push(remaining[i]);
            backtrack(current, [...remaining.slice(0, i), ...remaining.slice(i + 1)]);
            current.pop();
        }
    }
    backtrack([], nums);
    return result;
}

Combination Sum -- Find all combinations that sum to a target, where each number can be used unlimited times. Same backtracking structure, but pass the same start index (not i+1) to allow reuse, and prune when the running sum exceeds the target.

Backtracking Template

Python
def backtrack_template(candidates):
    result = []
    def backtrack(start, current, remaining_state):
        if is_valid_solution(current):
            result.append(current[:])
            return
        for i in range(start, len(candidates)):
            if should_prune(candidates[i]):
                continue
            current.append(candidates[i])       # choose
            backtrack(i + 1, current, new_state)  # explore
            current.pop()                        # un-choose
    backtrack(0, [], initial_state)
    return result

JavaScript
function backtrackTemplate(candidates) {
    const result = [];
    function backtrack(start, current, remainingState) {
        if (isValidSolution(current)) {
            result.push([...current]);
            return;
        }
        for (let i = start; i < candidates.length; i++) {
            if (shouldPrune(candidates[i])) continue;
            current.push(candidates[i]);
            backtrack(i + 1, current, newState);
            current.pop();
        }
    }
    backtrack(0, [], initialState);
    return result;
}

7. Prefix Sum

Precompute a running sum array so you can answer any "sum of subarray from i to j" query in O(1). The prefix sum at index i is the sum of all elements from index 0 through i.

Subarray Sum Equals K

Count the number of subarrays that sum to k. The brute force is O(n^2). The trick: use a hash map to store how many times each prefix sum has occurred. If current_prefix - k has been seen before, those are valid subarrays.

Python
def subarray_sum(nums, k):
    count = 0
    prefix = 0
    prefix_counts = {0: 1}  # empty prefix sum = 0 seen once

    for num in nums:
        prefix += num
        # If (prefix - k) was seen before, those are valid subarrays
        count += prefix_counts.get(prefix - k, 0)
        prefix_counts[prefix] = prefix_counts.get(prefix, 0) + 1

    return count

JavaScript
function subarraySum(nums, k) {
    let count = 0, prefix = 0;
    const prefixCounts = new Map([[0, 1]]);

    for (const num of nums) {
        prefix += num;
        count += (prefixCounts.get(prefix - k) || 0);
        prefixCounts.set(prefix, (prefixCounts.get(prefix) || 0) + 1);
    }
    return count;
}

Prefix Sum Template

Python
# Build prefix array
prefix = [0] * (len(arr) + 1)
for i in range(len(arr)):
    prefix[i + 1] = prefix[i] + arr[i]

# Range sum query: sum from index l to r (inclusive)
range_sum = prefix[r + 1] - prefix[l]

# Prefix sum + hash map (for subarray sum = k)
prefix = 0
seen = {0: 1}
for num in arr:
    prefix += num
    if prefix - k in seen:
        # found valid subarrays
        pass
    seen[prefix] = seen.get(prefix, 0) + 1

JavaScript
// Build prefix array
const prefix = new Array(arr.length + 1).fill(0);
for (let i = 0; i < arr.length; i++) {
    prefix[i + 1] = prefix[i] + arr[i];
}

// Range sum query: sum from index l to r (inclusive)
const rangeSum = prefix[r + 1] - prefix[l];

// Prefix sum + hash map (for subarray sum = k)
let pre = 0;
const seen = new Map([[0, 1]]);
for (const num of arr) {
    pre += num;
    if (seen.has(pre - k)) {
        // found valid subarrays
    }
    seen.set(pre, (seen.get(pre) || 0) + 1);
}

8. Monotonic Stack

A monotonic stack maintains elements in strictly increasing or decreasing order. When a new element violates the order, you pop from the stack -- and the popped elements have found their answer (the new element is their "next greater" or "next smaller").

Daily Temperatures

Given daily temperatures, for each day find how many days until a warmer temperature (or 0 if none).

Python
def daily_temperatures(temperatures):
    n = len(temperatures)
    result = [0] * n
    stack = []  # stores indices, monotonically decreasing temps

    for i in range(n):
        while stack and temperatures[i] > temperatures[stack[-1]]:
            prev = stack.pop()
            result[prev] = i - prev
        stack.append(i)

    return result

JavaScript
function dailyTemperatures(temperatures) {
    const n = temperatures.length;
    const result = new Array(n).fill(0);
    const stack = [];

    for (let i = 0; i < n; i++) {
        while (stack.length > 0 && temperatures[i] > temperatures[stack[stack.length - 1]]) {
            const prev = stack.pop();
            result[prev] = i - prev;
        }
        stack.push(i);
    }
    return result;
}

Next Greater Element

Given an array, find the next greater element for each position. Same approach as Daily Temperatures -- maintain a decreasing stack. When you encounter a larger element, pop all smaller elements from the stack: the larger element is their "next greater."

Monotonic Stack Template

Python
# Template: Next Greater Element (decreasing stack)
def next_greater(arr):
    n = len(arr)
    result = [-1] * n
    stack = []  # indices of elements waiting for their answer

    for i in range(n):
        while stack and arr[i] > arr[stack[-1]]:
            idx = stack.pop()
            result[idx] = arr[i]  # or (i - idx) for distance
        stack.append(i)
    return result

JavaScript
// Template: Next Greater Element (decreasing stack)
function nextGreater(arr) {
    const n = arr.length;
    const result = new Array(n).fill(-1);
    const stack = [];

    for (let i = 0; i < n; i++) {
        while (stack.length > 0 && arr[i] > arr[stack[stack.length - 1]]) {
            const idx = stack.pop();
            result[idx] = arr[i];
        }
        stack.push(i);
    }
    return result;
}

9. Greedy

A greedy algorithm makes the locally optimal choice at each step, hoping it leads to a globally optimal solution. The key question is always: can I prove that the greedy choice is safe?

• How to know greedy works: Can you prove that choosing the "best right now" never hurts? Does an exchange argument work (swapping any other choice makes it worse)?
• Common signal: Sort the input and then make greedy passes.

Jump Game

Given an array where each element is the max jump length from that position, determine if you can reach the last index.

Python
def can_jump(nums):
    farthest = 0
    for i in range(len(nums)):
        if i > farthest:
            return False  # can't reach this index
        farthest = max(farthest, i + nums[i])
    return True

JavaScript
function canJump(nums) {
    let farthest = 0;
    for (let i = 0; i < nums.length; i++) {
        if (i > farthest) return false;
        farthest = Math.max(farthest, i + nums[i]);
    }
    return true;
}

Merge Intervals

Sort intervals by start time. Scan through them: if the current interval overlaps with the previous one (current.start <= prev.end), merge them by extending the end. Otherwise, start a new group. Greedy because sorting + merging left-to-right never misses an overlap.

10. Interval Problems

Interval problems follow a consistent pattern: sort by start time, then process intervals left to right checking for overlaps.

Merge Intervals

Python
def merge(intervals):
    intervals.sort(key=lambda x: x[0])
    merged = [intervals[0]]

    for start, end in intervals[1:]:
        if start <= merged[-1][1]:  # overlaps with previous
            merged[-1][1] = max(merged[-1][1], end)  # extend
        else:
            merged.append([start, end])  # no overlap, new interval

    return merged

JavaScript
function merge(intervals) {
    intervals.sort((a, b) => a[0] - b[0]);
    const merged = [intervals[0]];

    for (let i = 1; i < intervals.length; i++) {
        const [start, end] = intervals[i];
        const prev = merged[merged.length - 1];
        if (start <= prev[1]) {
            prev[1] = Math.max(prev[1], end);
        } else {
            merged.push([start, end]);
        }
    }
    return merged;
}

11. Sweep Line

The sweep line (also called line sweep or event-based processing) technique converts a 2D or interval-based problem into a series of events sorted along one axis, then processes them in order. Instead of comparing every pair of objects (O(n^2)), you "sweep" through events left to right and maintain a data structure that tracks the current state.

Core Idea

The pattern has three steps:

1. Create events: Turn each object (interval, rectangle, etc.) into a pair of events -- a START event and an END event.
2. Sort events: Sort all events by their position along the sweep axis. Break ties carefully (usually starts before ends at the same position).
3. Sweep and maintain state: Process events left to right. Use a counter, heap, or balanced BST to track the "active" set. At each event, update your answer.

Given intervals: [1,4], [2,6], [5,8], [7,9]

Events (sorted):
  pos=1 START   pos=2 START   pos=4 END   pos=5 START   pos=6 END   pos=7 START   pos=8 END   pos=9 END

Sweep left to right, tracking active count:

  Active:  0    1       2      1       2       1       2       1       0

  Timeline:
  1────4
     2────────6
            5────────8
                  7──────9

  Maximum overlap: 2 (at positions 2-4 and 5-6 and 7-8)

Meeting Rooms II -- Minimum Rooms Needed

Given a list of meeting time intervals, find the minimum number of conference rooms required. This is the classic sweep line problem.

Python
def min_meeting_rooms(intervals):
    events = []
    for start, end in intervals:
        events.append((start, 1))   # +1 at start (meeting begins)
        events.append((end, -1))    # -1 at end (meeting ends)

    events.sort()  # sort by time; ties: ends (-1) before starts (+1)

    max_rooms = 0
    current_rooms = 0
    for time, delta in events:
        current_rooms += delta
        max_rooms = max(max_rooms, current_rooms)

    return max_rooms

# Example: [[0,30],[5,10],[15,20]]
# Events: (0,+1),(5,+1),(10,-1),(15,+1),(20,-1),(30,-1)
# Sweep:   1     2      1      2       1       0
# Answer: 2 rooms needed

JavaScript
function minMeetingRooms(intervals) {
    const events = [];
    for (const [start, end] of intervals) {
        events.push([start, 1]);   // meeting begins
        events.push([end, -1]);    // meeting ends
    }

    events.sort((a, b) => a[0] - b[0] || a[1] - b[1]);  // sort by time, ends before starts

    let maxRooms = 0, currentRooms = 0;
    for (const [time, delta] of events) {
        currentRooms += delta;
        maxRooms = Math.max(maxRooms, currentRooms);
    }

    return maxRooms;
}

The Skyline Problem

Given buildings represented as [left, right, height], compute the skyline outline. This is a harder sweep line problem that uses a max-heap to track the tallest active building.

Python
import heapq

def get_skyline(buildings):
    # Create events: (x, type, height)
    # Start: negative height (for max-heap via min-heap trick)
    # End: positive height
    events = []
    for left, right, height in buildings:
        events.append((left, -height, right))   # start event
        events.append((right, 0, 0))             # end event

    events.sort()  # sort by x; at same x, taller buildings first (negative height)

    # Max-heap: (-height, end_x). Start with ground level.
    result = []
    heap = [(0, float('inf'))]  # (neg_height, end_x) -- ground never ends

    for x, neg_h, end in events:
        if neg_h != 0:  # start event
            heapq.heappush(heap, (neg_h, end))
        # Remove buildings that have ended
        while heap[0][1] <= x:
            heapq.heappop(heap)

        max_height = -heap[0][0]
        if not result or result[-1][1] != max_height:
            result.append([x, max_height])

    return result

# Example: buildings = [[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]]
# Output: [[2,10],[3,15],[7,12],[12,0],[15,10],[20,8],[24,0]]

JavaScript
// Simplified approach using sorted events + tracking max height
function getSkyline(buildings) {
    const events = [];
    for (const [left, right, height] of buildings) {
        events.push([left, -height, right]);  // start: negative height
        events.push([right, 0, 0]);           // end event
    }
    events.sort((a, b) => a[0] - b[0] || a[1] - b[1]);

    // Use a sorted multiset or map to track active heights
    const active = new Map();  // height -> count
    active.set(0, 1);  // ground level always active
    const result = [];
    let prevMax = 0;

    for (const [x, negH, end] of events) {
        if (negH !== 0) {
            // Start event: add height
            const h = -negH;
            active.set(h, (active.get(h) || 0) + 1);
        } else {
            // End event: find and remove the building's height
            const bld = buildings.find(b => b[1] === x && active.has(b[2]));
            if (bld) {
                const h = bld[2];
                if (active.get(h) === 1) active.delete(h);
                else active.set(h, active.get(h) - 1);
            }
        }
        const curMax = Math.max(...active.keys());
        if (curMax !== prevMax) {
            result.push([x, curMax]);
            prevMax = curMax;
        }
    }
    return result;
}

My Calendar I -- Booking Without Conflicts

Implement a calendar that rejects overlapping bookings. Sweep line with sorted events makes checking conflicts efficient.

Python
class MyCalendar:
    def __init__(self):
        self.bookings = []

    def book(self, start, end):
        for s, e in self.bookings:
            if start < e and s < end:  # overlap check
                return False
        self.bookings.append((start, end))
        return True

# Optimized with sweep line for MyCalendar III (count max overlaps):
import collections

class MyCalendarThree:
    def __init__(self):
        self.timeline = collections.defaultdict(int)

    def book(self, start, end):
        self.timeline[start] += 1   # event begins
        self.timeline[end] -= 1     # event ends
        # Sweep through timeline
        active = 0
        max_k = 0
        for time in sorted(self.timeline):
            active += self.timeline[time]
            max_k = max(max_k, active)
        return max_k

JavaScript
class MyCalendarThree {
    constructor() {
        this.timeline = new Map();
    }

    book(start, end) {
        this.timeline.set(start, (this.timeline.get(start) || 0) + 1);
        this.timeline.set(end, (this.timeline.get(end) || 0) - 1);

        let active = 0, maxK = 0;
        const keys = [...this.timeline.keys()].sort((a, b) => a - b);
        for (const time of keys) {
            active += this.timeline.get(time);
            maxK = Math.max(maxK, active);
        }
        return maxK;
    }
}

Regular Interval Problems (sort by start, check neighbors):
  - Merge Intervals         → sort + linear scan
  - Insert Interval         → find position + merge
  - Non-Overlapping Count   → sort by end, greedy

Sweep Line Problems (convert to events, sweep with counter/heap):
  - Meeting Rooms II        → count max concurrent (events + counter)
  - The Skyline Problem     → track tallest active (events + max-heap)
  - Rectangle Area Union    → horizontal sweep + vertical sweep
  - My Calendar III         → count k-booking (events + counter)
  - Employee Free Time      → merge all intervals via sweep

Rule of thumb:
  If you need to count/track CONCURRENT or OVERLAPPING state → sweep line
  If you need to MERGE or CHECK neighbors → sort + scan

12. Pattern Recognition Cheat Sheet

When you read a problem, look for these clues to identify the right pattern. This is the single most valuable skill for LeetCode.

13. Practice Quiz

Given each problem description, identify which algorithm pattern you would use. Think about the clues before clicking an answer.