Skip to main content

20 LeetCode pattern

1. Prefix Sum​

The Prefix Sum pattern involves preprocessing an array to create a new array where each element at index i represents the sum of all elements from the start up to i. This allows for O(1) sum queries on any subarray.

When to use​

  • Multiple sum queries on subarrays
  • Finding subarrays with a target sum
  • Calculating cumulative totals

Template​

// Build prefix sum array
int[] prefix = new int[n + 1];
for (int i = 0; i < n; i++) {
    prefix[i + 1] = prefix[i] + nums[i];
}

// Query sum of range [left, right]
int rangeSum = prefix[right + 1] - prefix[left];

Practice Problems​

  1. Range Sum Query - Immutable LeetCode 303
  2. Contiguous Array LeetCode 525
  3. Subarray Sum Equals K LeetCode 560
  4. Product of Array Except Self LeetCode 238

2. Two Pointers​

The Two Pointers pattern uses two pointers to traverse an array or list, typically from opposite ends or both moving in the same direction. It reduces time complexity from O(n^2) to O(n) for many problems.

When to use​

  • Finding pairs in sorted arrays
  • Comparing elements from both ends
  • Partitioning arrays
  • Palindrome checks

Template​

// Opposite direction (converging)
int left = 0, right = n - 1;
while(left < right) {
     if (condition_met) {
        // found answer
     } else if (need_larger_sum) {
        left++;
     } else {
        right--;
     }
}

// Same direction
int slow = 0;
for (int fast = 0; fast < n; fast++) {
    if(condition) {
        // process and move slow
        slow++;
    }
}

Practice Problems​

  1. Two Sum II - Input Array is Sorted LeetCode 167
  2. 3Sum LeetCode 15
  3. Container With Most Water LeetCode 11
  4. Trapping Rain Water LeetCode 42
  5. Valid Palindrome LeetCode 125

3. Sliding Window​

The Sliding Window pattern maintains a window of elements and slides it across the array to find subarrays or substrings that satisfy certain conditions. It avoids recalculating overlapping parts of consecutive windows.

When to use​

  • Contiguous subarray/substring problems
  • Finding maximum/minimum in window of size k
  • Longest/shortest substring with certain properties
  • Problems involving consecutive elements

Template​

// Fixed-size window
int windowSum = 0;
for (int i = 0; i < n; i++) {
    windowSum += nums[i];
    if (i >= k - 1) {
        // process window
        result = Math.max(result, windowSum);
        windowSum -= nums[i - k + 1];
    }
}

// Variable-size window
int left = 0;
for (int right = 0; right < n; right++) {
    // expand window by including nums[right]

    while (window_condition_violated) {
        // shrink window from left
        left++;
    }

    // update result
}

Practice Problems​

  1. Maximum Average Subarray I LeetCode 643
  2. Longest Substring Without Repeating Characters LeetCode 3
  3. Minimum Window Substring LeetCode 76
  4. Permutation in String LeetCode 567
  5. Sliding Window Maximum LeetCode 239

4. Fast & Slow Pointers​

The Fast & Slow Pointers pattern (also called Tortoise and Hare) uses two pointers moving at different speeds. When there is a cycle, the fast pointer will eventually meet the slow pointer.

When to use​

  • Detecting cycles in linked lists or arrays
  • Finding the middle of a linked list
  • Finding the start of a cycle

Template​

// Find middle
while (fast != null && fast.next != null) {
    slow = slow.next;
    fast = fast.next.next;
}
return slow; // middle node

// Cycle detection
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
    slow = slow.next;
    fast = fast.next.next;

    if (slow == fast) {
        // cycle detected
        return true;
    }
}
return false; // no cycle

Practice Problems​

  1. Linked List Cycle LeetCode 141
  2. Linked List Cycle II LeetCode 142
  3. Happy Number LeetCode 202
  4. Find the Duplicate Number LeetCode 287
  5. Middle of the Linked List LeetCode 876

5. LinkedList In-place Reversal​

This pattern reverses parts of a linked list without using extra space. It manipulates pointers to reverse the direction of links.

When to use​

  • Reversing a linked list or portion of it
  • Reversing nodes in groups
  • Checking for palindromes in linked lists

Template​

// Reverse entire list
ListNode prev = null, curr = head;
while (curr != null) {
    ListNode next = curr.next;
    curr.next = prev;
    prev = curr;
    curr = next;
}
return prev; // new head

Practice Problems​

  1. Reverse Linked List LeetCode 206
  2. Reverse Linked List II LeetCode 92
  3. Swap Nodes in Pairs LeetCode 24
  4. Reverse Nodes in k-Group LeetCode 25
  5. Palindrome Linked List LeetCode 234