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 ([https://leetcode.com/problems/range-sum-query-immutable](LeetCode 303))
2. Contiguous Array ([https://leetcode.com/problems/contiguous-array](LeetCode 525))
3. Subarray Sum Equals K ([https://leetcode.com/problems/subarray-sum-equals-k/](LeetCode 560))
4. Product of Array Except Self ([https://leetcode.com/problems/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 ([https://leetcode.com/problems/two-sum-ii-input-array-is-sorted](LeetCode 167))
2. 3Sum ([https://leetcode.com/problems/3sum](LeetCode #15))
3. Container With Most Water ([https://leetcode.com/problems/container-with-most-water](LeetCode 11))
4. Trapping Rain Water ([https://leetcode.com/problems/trapping-rain-water](LeetCode 42))
5. Valid Palindrome ([https://leetcode.com/problems/valid-palindrome](LeetCode 125))