See all coding puzzles and patterns here.

---

Algorithm Description

A prefix sum algorithm is used for various problems, usually those involving sums of sub-arrays.

This technique involves computing the sum of each prefix in an array and then using those prefix sums to compute sums of subarrays by subtracting the sum immediately before the start of the sub-array from the sum immediately at the end of the sub-array.

---

Performance Characteristics

Let $n =$ the number of items in the input array

Then the core prefix sum algorithm has a runtime complexity of $O(n)$.

Because an auxiliary list of prefix sums is being created, auxiliary space complexity of the algorithm is also $O(n)$.

---

Puzzles

Puzzle	Difficulty	External Link
Continuous Subarray Sum	Medium	Leetcode 523