LC 2025

References

Problem List

Data Structures

Basic

1. Enumerate the right, maintain the left.

Core Concept: For two-variable problems like the two-sum where a_i + a_j = t:

  • Enumerate the right-hand variable a_j
  • Transform into a single-variable problem: find a_i = t - a_j
  • Use a hash table to maintain previously seen left elements

Implementation Pattern:

def two_sum_pattern(arr, target):
    seen = {}  # Hash table for left elements

    for j, a_j in enumerate(arr):
        complement = target - a_j
        if complement in seen:
            return [seen[complement], j]
        seen[a_j] = j

    return None

2. Enumerate the middle.

Core Concept: When dealing with multiple variables with ordering constraints, enumerate the middle variable to automatically separate the problem space.

Strategy Best For Time Space Key Tool
Right Enumeration 2-variable problems O(n) O(n) Hash table
Middle Enumeration 3+ variable problems O(n²) O(1) Two pointers

Implementation Pattern:

def three_sum_pattern(arr):
    arr.sort()  # Enable two-pointer technique
    result = []

    for j in range(1, len(arr) - 1):  # Enumerate middle
        left, right = 0, len(arr) - 1

        while left < j and right > j:
            current_sum = arr[left] + arr[j] + arr[right]

            if current_sum == target:
                result.append([arr[left], arr[j], arr[right]])
                left += 1
                right -= 1
            elif current_sum < target:
                left += 1
            else:
                right -= 1

    return result

Prefix Sum

1. Left-Closed Right-Open Formula

Core Concept: For the sum of elements in the left-closed right-open interval [left, right):

Range Sum = sum[right] - sum[left]

Where:

  • sum[i] represents the sum of the first i elements (i.e., arr[0] + arr[1] + ... + arr[i-1])
  • Interval [left, right) includes left but excludes right

Implementation Template:

def build_prefix_sum(arr):
    """
    Build prefix sum array
    sum[i] represents the sum of first i elements
    """
    n = len(arr)
    prefix_sum = [0] * (n + 1)  # Length n+1 for easier boundary handling
    
    for i in range(n):
        prefix_sum[i + 1] = prefix_sum[i] + arr[i]
    
    return prefix_sum
def range_sum(prefix_sum, left, right):
    """
    Query sum of interval [left, right)
    Time Complexity: O(1)
    """
    return prefix_sum[right] - prefix_sum[left]
class PrefixSum:
    def __init__(self, arr):
        """Initialize prefix sum array"""
        self.n = len(arr)
        self.prefix = [0] * (self.n + 1)
        
        # Build prefix sum
        for i in range(self.n):
            self.prefix[i + 1] = self.prefix[i] + arr[i]
    
    def query(self, left, right):
        """
        Query sum of interval [left, right)
        
        Args:
            left: Left boundary (inclusive)
            right: Right boundary (exclusive)
            
        Returns:
            Range sum
        """
        return self.prefix[right] - self.prefix[left]

# Usage Example
arr = [1, 2, 3, 4, 5]
ps = PrefixSum(arr)

# Query different intervals
print(ps.query(0, 3))  # [0, 3) -> 1+2+3 = 6
print(ps.query(1, 4))  # [1, 4) -> 2+3+4 = 9
print(ps.query(2, 5))  # [2, 5) -> 3+4+5 = 12