Codacoda
Back to Academy

patterns

Prefix Sum

Prefix sum precomputes cumulative sums so that any subarray sum can be answered in O(1) time. By storing the running total at each index, the sum of elements from index i to j equals prefix[j+1] - prefix[i]. This transforms repeated range-sum queries from O(n) each to O(1) after an O(n) preprocessing step.

Use Cases

  • •Answering multiple range sum queries efficiently
  • •Finding subarrays that sum to a given target
  • •Computing running averages and cumulative statistics

Complexity Analysis

MetricBestAverageWorst
TimeO(n)O(n)O(n)
SpaceO(n)

Visualization

1234501234
Speed:1x
Array: [1, 2, 3, 4, 5]. Build prefix sum array.Step 1 / 8

Implementation

Output

Click "Run Code" to see output...