CodeMosa

Master LeetCode Patterns

IntermediateArrays & StringsRead Arrays & Strings Fundamentals →

Prefix/Suffix Arrays

Precompute cumulative information to answer range queries efficiently

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

What is Prefix/Suffix Arrays?

#
Definition: Precompute cumulative values (sum/XOR/difference) to answer range queries in O(1) and support batch range updates.

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.

How Prefix/Suffix Arrays works

#

Prefix sums enable O(1) range queries; difference arrays enable O(1) range updates with an O(n) final prefix build.

  • Multiple range sum/product queries
  • Subarray sum equals k problems
  • Finding equilibrium or pivot points

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

Code Templates

#
Prefix sums enable O(1) range queries; difference arrays enable O(1) range updates with an O(n) final prefix build.
# 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

Pattern Variants & Approaches

#
Different methodologies and implementations for this pattern
1

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
2

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
3

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

Related Patterns

#
Hash Map / Hash TableSliding WindowTwo Pointers

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