Prefix Sum Patterns: Complete Reference¶

def build_prefix_sum(nums: List[int]) -> List[int]:
    """
    Build prefix sum array.

    prefix[i] = sum of nums[0..i-1] (elements BEFORE index i)
    Range sum [left, right] = prefix[right+1] - prefix[left]

    Why prefix[0] = 0?
    - Handles range queries starting at index 0: sum[0..right] = prefix[right+1] - prefix[0]
    - Without it, we'd need special case handling for left=0
    """
    prefix = [0]  # Empty prefix
    for num in nums:
        prefix.append(prefix[-1] + num)
    return prefix

class NumArray:
    """
    Range sum query with O(n) preprocessing and O(1) queries.

    Prefix Sum Mechanics:
    - prefix[0] = 0 (empty prefix, handles edge case of full array sum)
    - prefix[i] = sum(nums[0:i])
    - Range sum [left, right] = prefix[right+1] - prefix[left]

    Why prefix[right+1] - prefix[left]?
    prefix[right+1] = nums[0] + nums[1] + ... + nums[right]
    prefix[left]    = nums[0] + nums[1] + ... + nums[left-1]
    Difference      = nums[left] + nums[left+1] + ... + nums[right]

    Time: O(n) init, O(1) query | Space: O(n)
    """
    def __init__(self, nums: List[int]):
        # Initialize with 0 for empty prefix
        self.prefix_sum: List[int] = [0]
        for num in nums:
            self.prefix_sum.append(self.prefix_sum[-1] + num)

    def sumRange(self, left: int, right: int) -> int:
        return self.prefix_sum[right + 1] - self.prefix_sum[left]

class SolutionPrefixSum:
    """
    Count subarrays with sum = k using prefix sum + hash map.

    Algorithm:
    1. Track running prefix sum
    2. For each position, count how many times (prefix_sum - k) appeared before
    3. Record current prefix sum for future positions

    Why Initialize {0: 1}?
    - Handles subarrays starting from index 0
    - If prefix_sum == k at position i, the subarray [0..i] sums to k
    - We need to count the "empty prefix" (sum 0 before index 0)

    Time: O(n) | Space: O(n)
    """
    def subarraySum(self, nums: List[int], k: int) -> int:
        subarray_count = 0
        prefix_sum = 0

        # Map: prefix_sum value -> count of occurrences
        # Initialize with {0: 1} for subarrays starting at index 0
        sum_frequency: dict[int, int] = {0: 1}

        for num in nums:
            # Extend prefix sum with current element
            prefix_sum += num

            # Count subarrays ending here with sum = k
            # If (prefix_sum - k) was seen before, those positions mark valid starts
            complement = prefix_sum - k
            subarray_count += sum_frequency.get(complement, 0)

            # Record current prefix sum for future elements
            sum_frequency[prefix_sum] = sum_frequency.get(prefix_sum, 0) + 1

        return subarray_count

class SolutionTransform:
    """
    Find longest subarray with equal 0s and 1s.

    Transform Technique:
    1. Replace 0 with -1 in the conceptual array
    2. Problem becomes: find longest subarray with sum = 0
    3. Use prefix sum + hash map (first occurrence)

    Why First Occurrence?
    - To maximize length, we want earliest position with same prefix sum
    - prefix[j] - prefix[i] = 0 means subarray (i, j] is balanced
    - Smaller i = longer subarray

    Time: O(n) | Space: O(n)
    """
    def findMaxLength(self, nums: List[int]) -> int:
        max_length = 0
        prefix_sum = 0

        # Map: prefix_sum value -> first index where this sum occurred
        # Initialize with {0: -1} for subarrays starting at index 0
        first_occurrence: dict[int, int] = {0: -1}

        for index, num in enumerate(nums):
            # Transform: treat 0 as -1
            prefix_sum += 1 if num == 1 else -1

            if prefix_sum in first_occurrence:
                # Found a balanced subarray from (first_occurrence + 1) to current
                length = index - first_occurrence[prefix_sum]
                max_length = max(max_length, length)
            else:
                # Record first occurrence for maximum length
                first_occurrence[prefix_sum] = index

        return max_length

class SolutionModular:
    """
    Check if subarray of size >= 2 sums to multiple of k.

    Modular Arithmetic Insight:
    - (prefix[j] - prefix[i]) % k == 0 iff prefix[j] % k == prefix[i] % k
    - Track first occurrence of each remainder
    - Ensure subarray length >= 2: j - i >= 2

    Edge Case: k = 0 is not possible per constraints (k >= 1)

    Time: O(n) | Space: O(min(n, k))
    """
    def checkSubarraySum(self, nums: List[int], k: int) -> bool:
        # Map: remainder -> first index with this remainder
        # Initialize with {0: -1} for subarrays starting at index 0
        remainder_first_index: dict[int, int] = {0: -1}
        prefix_sum = 0

        for index, num in enumerate(nums):
            prefix_sum += num
            remainder = prefix_sum % k

            if remainder in remainder_first_index:
                # Check if subarray length >= 2
                if index - remainder_first_index[remainder] >= 2:
                    return True
            else:
                # Only store first occurrence (to maximize length)
                remainder_first_index[remainder] = index

        return False

class NumMatrix:
    """
    2D range sum query with O(m*n) preprocessing and O(1) queries.

    Prefix Sum 2D:
    - Extra row and column of zeros simplify boundary handling
    - prefix[i][j] = sum of rectangle from (0,0) to (i-1, j-1)
    - Uses inclusion-exclusion principle for both building and querying

    Time: O(m*n) init, O(1) query | Space: O(m*n)
    """
    def __init__(self, matrix: List[List[int]]):
        if not matrix or not matrix[0]:
            self.prefix_sum = [[0]]
            return

        row_count, col_count = len(matrix), len(matrix[0])

        # Extra row and column of zeros for boundary handling
        self.prefix_sum = [[0] * (col_count + 1) for _ in range(row_count + 1)]

        # Build prefix sum using inclusion-exclusion
        for row in range(1, row_count + 1):
            for col in range(1, col_count + 1):
                self.prefix_sum[row][col] = (
                    matrix[row - 1][col - 1]
                    + self.prefix_sum[row - 1][col]      # Top rectangle
                    + self.prefix_sum[row][col - 1]      # Left rectangle
                    - self.prefix_sum[row - 1][col - 1]  # Subtract overlap
                )

    def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
        return (
            self.prefix_sum[row2 + 1][col2 + 1]  # Total (origin to bottom-right)
            - self.prefix_sum[row1][col2 + 1]    # Subtract top strip
            - self.prefix_sum[row2 + 1][col1]    # Subtract left strip
            + self.prefix_sum[row1][col1]        # Add back top-left (subtracted twice)
        )

class SolutionPrefixSuffix:
    """
    Compute product of array except self without division.

    Two-pass Approach:
    1. Left-to-right: Build prefix products in result array
    2. Right-to-left: Multiply by suffix products using single variable

    Why No Division?
    - Problem explicitly forbids it (challenge constraint)
    - Division fails with zeros in the array
    - This approach handles zeros correctly

    Time: O(n) | Space: O(1) excluding output
    """
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        array_length = len(nums)
        result = [1] * array_length

        # Pass 1: Build prefix products
        # After this pass, result[i] = product of nums[0..i-1]
        prefix_product = 1
        for index in range(array_length):
            result[index] = prefix_product
            prefix_product *= nums[index]

        # Pass 2: Multiply by suffix products
        # After this pass, result[i] = prefix[0..i-1] * suffix[i+1..n-1]
        suffix_product = 1
        for index in range(array_length - 1, -1, -1):
            result[index] *= suffix_product
            suffix_product *= nums[index]

        return result

class SolutionDifferenceArray:
    """
    Check if car pooling is feasible using difference array.

    Difference Array Technique:
    1. Record passenger changes at pickup/dropoff locations
    2. Prefix sum gives actual passenger count at each location
    3. Verify no location exceeds capacity

    Key Insight:
    - Passengers board at 'from' location
    - Passengers exit at 'to' location (NOT inclusive - they're gone before 'to')
    - This creates range [from, to) updates

    Time: O(n + m) where n = trips, m = max location | Space: O(m)
    """
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        # Find max location to determine array size
        max_location = max(trip[2] for trip in trips)

        # Difference array: diff[i] = change in passenger count at location i
        passenger_change = [0] * (max_location + 1)

        # Build difference array
        for passengers, pickup_location, dropoff_location in trips:
            passenger_change[pickup_location] += passengers    # Passengers board
            passenger_change[dropoff_location] -= passengers   # Passengers exit

        # Prefix sum to compute actual passenger count at each location
        current_passengers = 0
        for delta in passenger_change:
            current_passengers += delta
            if current_passengers > capacity:
                return False

        return True

class SolutionDifferenceArray:
    """
    Compute total seats reserved for each flight using difference array.

    Difference Array Mechanics:
    - diff[i] = change in seat count at flight i
    - To add 'seats' to range [first, last] (1-indexed):
      diff[first-1] += seats   (start adding, convert to 0-indexed)
      diff[last] -= seats      (stop adding after last)
    - Prefix sum reconstructs actual seat counts

    Why O(n + m)?
    - O(m) to process all bookings (each is O(1))
    - O(n) to compute prefix sum
    - Much better than O(n * m) naive approach

    Time: O(n + m) where n = flights, m = bookings | Space: O(n)
    """
    def corpFlightBookings(self, bookings: List[List[int]], n: int) -> List[int]:
        # Difference array: diff[i] = change in seat count at flight i
        # Use n+1 to handle the boundary case when last == n
        seat_change = [0] * (n + 1)

        # Apply range updates using difference array technique
        for first_flight, last_flight, seat_count in bookings:
            # Convert to 0-indexed: first_flight=1 -> index 0
            seat_change[first_flight - 1] += seat_count    # Start adding seats
            seat_change[last_flight] -= seat_count         # Stop after last flight

        # Prefix sum to reconstruct actual seat counts
        total_seats = []
        current_seats = 0
        for flight_index in range(n):
            current_seats += seat_change[flight_index]
            total_seats.append(current_seats)

        return total_seats

# Build prefix sum
prefix = [0]
for num in nums:
    prefix.append(prefix[-1] + num)

# Query [left, right]
range_sum = prefix[right + 1] - prefix[left]

count = 0
prefix_sum = 0
sum_count = {0: 1}  # Initialize with empty prefix

for num in nums:
    prefix_sum += num
    count += sum_count.get(prefix_sum - k, 0)
    sum_count[prefix_sum] = sum_count.get(prefix_sum, 0) + 1

max_length = 0
prefix_sum = 0
first_occurrence = {0: -1}  # Initialize at "index -1"

for index, num in enumerate(nums):
    prefix_sum += num  # Or transformed value
    if prefix_sum in first_occurrence:
        max_length = max(max_length, index - first_occurrence[prefix_sum])
    else:
        first_occurrence[prefix_sum] = index

# Build difference array
diff = [0] * (n + 1)
for start, end, value in updates:
    diff[start] += value
    diff[end + 1] -= value  # Stop after end

# Reconstruct with prefix sum
result = []
current = 0
for i in range(n):
    current += diff[i]
    result.append(current)

# Build 2D prefix sum (with boundary zeros)
prefix = [[0] * (cols + 1) for _ in range(rows + 1)]
for i in range(1, rows + 1):
    for j in range(1, cols + 1):
        prefix[i][j] = (matrix[i-1][j-1]
                       + prefix[i-1][j]
                       + prefix[i][j-1]
                       - prefix[i-1][j-1])

# Query rectangle (r1, c1) to (r2, c2)
def query(r1, c1, r2, c2):
    return (prefix[r2+1][c2+1] - prefix[r1][c2+1]
           - prefix[r2+1][c1] + prefix[r1][c1])

n = len(nums)
result = [1] * n

# Forward pass: prefix products
prefix = 1
for i in range(n):
    result[i] = prefix
    prefix *= nums[i]

# Backward pass: multiply by suffix products
suffix = 1
for i in range(n - 1, -1, -1):
    result[i] *= suffix
    suffix *= nums[i]