Arrays, Subarrays & Prefix Sums

Why this is where the roadmap starts

Almost every pattern later in this roadmap — Two Pointers, Sliding Window, Stack, even Binary Search — is a specialized way of walking or searching an array. Before you get to those, you need the array's most basic superpower: precomputing information about it once, in O(n), so that questions about any subrange can be answered without re-scanning. That precomputation is the prefix sum, and recognizing when a problem wants it (versus a two-pointer or sliding-window pass) is a core piece of interview pattern-matching.

Recognizing the pattern

Reach for prefix sums when a problem statement has any of these shapes:

• "Sum (or product, XOR, count) of elements between index i and j" — especially if this is asked repeatedly for different (i, j) pairs.
• "Find a subarray whose sum equals/exceeds/is divisible by some value k", and the array can contain negative numbers. (If all values are positive, Sliding Window is usually the better tool — see that topic. Negative values break the sliding window's monotonicity, which is exactly when prefix sums take over.)
• "Split the array into two parts with equal sum" or "find an index where the sums on either side balance."
• Anything phrased in terms of a contiguous subarray (not subsequence) and an aggregate over it.

The tell is repeated range queries over a static array. If you find yourself about to write nested loops where the inner loop re-sums a range for every outer index, that's an O(n^2) smell — a prefix array almost always gets you to O(n) preprocessing + O(1) per query.

The core technique

Given nums, define prefix[i] as the sum of nums[0..i-1] (0-indexed, with prefix[0] = 0 as a sentinel for "empty prefix"). Then:

The invariant that makes this work: sum(nums[l..r]) = prefix[r+1] - prefix[l]. Once prefix is built, every range-sum query is O(1), no matter how many times you ask.

The prefix[0] = 0 sentinel is the detail people forget and then get off-by-one errors from. It lets you query a range starting at index 0 without a special case (range_sum(prefix, 0, r) == prefix[r+1] - prefix[0] == prefix[r+1]).

Variations you should recognize

Prefix sums generalize to any associative, invertible operation, and the "prefix" idea extends in a few directions that show up constantly in interviews:

Variation	What it answers	Key idea
Prefix sum	Sum of nums[l..r]	prefix[r+1] - prefix[l]
Suffix sum	Sum of nums[l..r] from the right	Mirror of prefix sum, built right-to-left
Prefix/suffix aggregate (min, max, product)	"Best value to the left/right of i"	Same one-pass construction, swap + for min/max/*
Prefix XOR	XOR of nums[l..r]	XOR is its own inverse: prefix[r+1] ^ prefix[l]
Difference array	Apply many range updates, then read final array once	Inverse of prefix sum — see below
2D prefix sum	Sum of a sub-rectangle in a matrix	Inclusion-exclusion over 4 corners

Prefix/suffix aggregates (min, max, or product instead of sum) are especially common: any problem asking "what's the best/largest/smallest value to the left of index i, precomputed for every i" wants a prefix-aggregate array, built with the identical one-pass loop as prefix sum, just with a different combining operator. This is the same shape used by Product of Array Except Self (combine prefix and suffix aggregates from both sides) and by Trapping Rain Water (track the running max seen so far from each direction) — both listed below; work out the exact combination step yourself.

Real-world case study: integral images and real-time face detection. The 2D prefix sum in the table above has a specific, famous name in computer vision — the integral image — and it's the reason the 2001 Viola–Jones face detector could run in real time on CPUs of that era. Face detection scans a huge number of candidate rectangular windows at many scales and positions, and at each one needs the sum of pixel intensities inside that rectangle (as a building block for Haar-like features, which compare sums of adjacent rectangular regions). Computing each rectangle's sum by rescanning its pixels is exactly the O(n²)-per-query brute force this subtopic opens with — over millions of candidate windows per frame, that's nowhere close to real time. Precomputing one integral image with the same inclusion-exclusion formula from the pitfalls below turns every candidate rectangle's sum into an O(1) lookup (4 array accesses, regardless of the rectangle's size), which is precisely what made real-time face detection on 2001-era hardware feasible — the same "precompute once in O(n), answer any range query in O(1)" trade this whole subtopic is built around, just extended to two dimensions and applied to a problem that looks nothing like "array" at first glance.

Difference arrays flip the direction: instead of many read queries on a static array, you have many range-update queries ("add v to every element in [l, r]") and only need to read the final array once. Instead of updating each element in the range (O(n) per update), you mark diff[l] += v and diff[r+1] -= v, then take the prefix sum of diff at the end to materialize the final array in one O(n) pass:

This turns O(n * updates) into O(n + updates), and it's the same trick you'll see again in the Intervals topic when sweeping over many ranges at once.

Real-world case study: booking and reservation systems. "Add v to every day/slot in a date range" is exactly what a hotel, calendar, or rental-inventory system does on every new booking — decrement available capacity across a contiguous range of dates. Naively walking every day in the range on every booking is fine at small scale, but a difference array turns each booking into two O(1) point updates, with the actual per-day capacity only materialized (via one prefix-sum pass) when it's read — e.g., once per day for a dashboard, not once per booking. This is the same "many cheap writes, one amortized read" trade-off you'll see formalized as lazy propagation in the Trees topic's segment tree material, just without needing a tree at all when the queries are simple range-add-then-read-everything, rather than arbitrary interleaved range queries.

Prefix sums + hash maps: the other half of this pattern

The single most valuable extension of prefix sums pairs them with a hash map (full mechanics of hash maps are covered in the next subtopic — here, just treat it as an O(1)-average lookup table). The insight: if two indices i < j have the same prefix sum, then the subarray between them sums to zero; more generally, if prefix[j] - prefix[i] == target, then the subarray from i+1 to j sums to exactly target. Instead of checking every pair of prefix values (O(n^2)), store each prefix sum's index (or count) in a hash map as you go, and look up the complement you need at each step — collapsing the search to O(n).

Concretely, to find the length of the longest subarray summing to zero: walk the array while tracking a running sum, and store the first index at which each running-sum value was seen (seed the map with {0: -1} so a zero-sum subarray starting at index 0 is handled without a special case). Every time the running sum repeats a value you've seen before, the subarray between those two indices sums to zero — compare its length against your best answer. The same shape — track a running aggregate, look up what you need in a map, decide whether to update or insert — is exactly what you'll reuse for counting subarrays with a target sum and for the "treat 0/1 as ±1" trick on binary arrays, both in the problem set below.

Complexity analysis

Approach	Preprocessing	Per-query time	Space
Brute force (re-sum each query)	O(1)	O(n)	O(1)
All-pairs precompute (sum[i][j] for every pair)	O(n^2)	O(1)	O(n^2)
Prefix sum array	O(n)	O(1)	O(n)
Prefix sum, computed in place	O(n)	O(1)	O(1) extra (destroys input)

For a single pass with no repeated queries, a running total is enough (O(1) space); you only need the full prefix array when you must answer range queries at arbitrary, previously-unknown indices — including the "look up a past prefix value" pattern above, where the array (or hash map) is the set of queries you'll need to answer later.

Common pitfalls

• Off-by-one on the prefix array's length. Using a prefix array of length n (instead of n + 1) forces awkward if l == 0 special cases. Always allocate n + 1 and let prefix[0] = 0 absorb the edge case.
• Confusing inclusive/exclusive ranges. Decide once whether prefix[i] means "sum up to and including i" or "sum of the first i elements" (exclusive) and stay consistent — mixing conventions is the #1 source of bugs here.
• Forgetting the sentinel when pairing with a hash map. As above, seed the map with {0: -1} (or {0: 1} for a counting variant) so subarrays starting at index 0 aren't silently missed.
• Reaching for prefix sums when sliding window would be simpler and use less space. If all values are non-negative and you want a contiguous range satisfying a sum constraint, Sliding Window (its own topic) is typically O(1) space instead of O(n) — prefix sums are the fallback for when negative numbers break that monotonicity.
• Integer overflow in languages with fixed-width integers (not a concern in Python, but say it out loud in an interview if you're asked to reason about it in Java/C++ — cumulative sums can exceed 32-bit range even when individual elements don't).
• 2D prefix sums: get the inclusion-exclusion formula backwards. For a sub-rectangle sum, it's S(r2,c2) - S(r1-1,c2) - S(r2,c1-1) + S(r1-1,c1-1) — the last term is added back because it was subtracted twice.

How to talk about it in an interview

State the reframing explicitly before you code: "I'll precompute a prefix sum array in O(n), which turns every range-sum query into an O(1) lookup — so the total is O(n + q) for q queries instead of O(n·q)." If a hash map is involved, name the invariant: "since prefix[j] - prefix[i] = target is what I'm looking for, I can store prefix values I've already seen in a hash map and look up the complement in O(1) as I go, turning an O(n^2) pair search into O(n)."