IntermediateArrays & Strings

Prefix/Suffix Arrays

Precompute cumulative information to answer range queries efficiently

Time: O(n) preprocessing, O(1) query

Space: O(n)

Pattern Overview

Core Idea

Prefix arrays store cumulative information from the start of the array, while suffix arrays store information from the end. This preprocessing enables O(1) range queries for sums, products, XOR, or other associative operations.

When to Use

Use when you need to answer multiple range queries efficiently, calculate subarray sums, find equilibrium points, or solve problems involving cumulative operations. Particularly useful when queries are more frequent than updates.

General Recognition Cues

General indicators that this pattern might be applicable

Multiple range sum/product queries
Subarray sum equals k problems
Finding equilibrium or pivot points
XOR queries on ranges
Difference array for range updates
Need O(1) query time after preprocessing

Pattern Variants & Approaches

Different methodologies and implementations for this pattern

Prefix Sum Array

Store cumulative sums to answer range sum queries in O(1)

When to Use This Variant

Subarray sum queries
Range sum calculations
Finding subarrays with target sum
Equilibrium index problems
Multiple sum queries on same array

Use Case

Range sum queries, subarray sum problems, equilibrium index

Advantages

O(1) query time after O(n) preprocessing
Simple to implement and understand
Works with any associative operation
Memory efficient (O(n) space)

Implementation

def prefix_sum(arr):
      n = len(arr)
      prefix = [0] * (n + 1)
      
      # Build prefix sum array
      for i in range(n):
          prefix[i + 1] = prefix[i] + arr[i]
      
      return prefix
  
  def range_sum(prefix, left, right):
      # Sum of arr[left:right+1]
      return prefix[right + 1] - prefix[left]
  
  # Example: Subarray sum equals k
  def subarray_sum_k(arr, k):
      count = 0
      prefix_sum = 0
      sum_freq = {0: 1}  # Handle subarrays starting at index 0
      
      for num in arr:
          prefix_sum += num
          
          # Check if (prefix_sum - k) exists
          if prefix_sum - k in sum_freq:
              count += sum_freq[prefix_sum - k]
          
          sum_freq[prefix_sum] = sum_freq.get(prefix_sum, 0) + 1
      
      return count

Prefix XOR

Use XOR properties to solve range XOR queries and bit manipulation problems

When to Use This Variant

XOR queries on ranges
Finding missing/duplicate numbers
Subarray XOR equals k
Bit manipulation problems
XOR has self-inverse property

Use Case

Range XOR queries, finding missing numbers, XOR subarray problems

Advantages

XOR is self-inverse (a ^ a = 0)
Useful for bit manipulation
Handles duplicate detection
Works with binary properties

Implementation

def prefix_xor(arr):
      n = len(arr)
      prefix = [0] * (n + 1)
      
      for i in range(n):
          prefix[i + 1] = prefix[i] ^ arr[i]
      
      return prefix
  
  def range_xor(prefix, left, right):
      # XOR of arr[left:right+1]
      return prefix[right + 1] ^ prefix[left]
  
  # Example: Subarray XOR equals k
  def subarray_xor_k(arr, k):
      count = 0
      xor_sum = 0
      xor_freq = {0: 1}
      
      for num in arr:
          xor_sum ^= num
          
          # Check if (xor_sum ^ k) exists
          target = xor_sum ^ k
          if target in xor_freq:
              count += xor_freq[target]
          
          xor_freq[xor_sum] = xor_freq.get(xor_sum, 0) + 1
      
      return count

Difference Array

Efficiently handle multiple range updates with O(1) per update

When to Use This Variant

Multiple range increment/decrement operations
Range update queries
Final array state after many updates
Batch processing of range modifications
O(1) update time required

Use Case

Range updates, batch modifications, timeline problems

Advantages

O(1) per range update
Efficient for many updates
Simple to implement
Works with any additive operation

Implementation

def difference_array(n):
      return [0] * (n + 1)
  
  def range_update(diff, left, right, val):
      # Add val to range [left, right]
      diff[left] += val
      diff[right + 1] -= val
  
  def build_final_array(diff):
      n = len(diff) - 1
      result = [0] * n
      current = 0
      
      for i in range(n):
          current += diff[i]
          result[i] = current
      
      return result
  
  # Example: Corporate Flight Bookings
  def corp_flight_bookings(bookings, n):
      diff = [0] * (n + 1)
      
      for first, last, seats in bookings:
          diff[first - 1] += seats
          diff[last] -= seats
      
      result = []
      current = 0
      for i in range(n):
          current += diff[i]
          result.append(current)
      
      return result

Common Pitfalls

Watch out for these common mistakes

Off-by-one errors in index calculations
Not handling empty subarrays correctly
Forgetting to handle negative numbers in prefix sums
Incorrect range calculation (should be prefix[j+1] - prefix[i])
Not considering overflow for large cumulative values

Code Templates

Compare implementations across different languages

# Prefix Sum Template
  def prefix_sum(arr):
      n = len(arr)
      prefix = [0] * (n + 1)
      for i in range(n):
          prefix[i + 1] = prefix[i] + arr[i]
      return prefix
  
  def range_sum(prefix, left, right):
      return prefix[right + 1] - prefix[left]
  
  # Difference Array Template
  def range_update(diff, left, right, val):
      diff[left] += val
      diff[right + 1] -= val
  
  def build_array(diff):
      result = []
      current = 0
      for val in diff[:-1]:
          current += val
          result.append(current)
      return result

Example Problems

Classic LeetCode problems using this pattern

Complexity Analysis

Time Complexity

O(n) preprocessing, O(1) query

Building prefix array takes O(n), each query is O(1). Range updates are O(1) with difference array.

Space Complexity

O(n)

Requires O(n) space to store the prefix/suffix/difference array.

Ready to test your knowledge?

Test your pattern recognition with interactive questions