Prefix Sums, Two Pointers & Sliding Window

Many array problems ask about ranges: the sum of a slice, the shortest stretch that reaches a goal, a pair that adds up. Three small tricks turn these from O(n²) into O(n).

intermediate⏱ 14 min read

←Builds on

1Arrays & Dynamic ArraysPrefix sums are a second array where any range sum is two O(1) lookups.0Big-O & Growth RatesBoth tricks turn O(n²) nested loops into a single O(n) pass.1Hash Tables: Sets & MapsCounting subarrays with a given sum stores the prefix sums seen so far in a hash map.

Leads to→

2Quicksort & PartitioningPartitioning is two pointers walking toward each other and swapping misplaced elements.2Counting SortPrefix sums of the counts tell each key where its block starts in the output.5Fenwick Tree (Binary Indexed Tree)Prefix sums answer a range in O(1) but must be recounted after every change; a Fenwick tree keeps both fast.11Naive Pattern MatchingThe naive matcher slides a window of length m across the text.+Z-FunctionIt keeps a window [l, r] of the rightmost match to skip comparisons it already made.

1Learn 2Play 3Check 4Practice

Learn

The idea, the mechanics and the cost.

01Prefix sums: precompute once, answer instantly

Summing a[l..r] with a loop costs O(n) per question. With a million questions that is too slow.

Instead, build prefix sums once: p[0] = 0 and p[i+1] = p[i] + a[i]. So p[i] is the sum of the first i elements.

Now any range sum is one subtraction:

sum(a[l..r]) = p[r+1] − p[l]

p[r+1] covers everything up to r, and p[l] removes the part before l. In the picture: a[2..5] = p[6] − p[2] = 23 − 4 = 19.

Building is O(n), every query is O(1). Watch the off-by-one: p has n+1 entries, and p[i] means "before index i".

02Two pointers on a sorted array

Find two numbers in a sorted array that add up to a target. Checking all pairs is O(n²). Instead, put pointer L at the start and R at the end:

if a[L] + a[R] is too small, the only way to grow it is to move L right
if it is too big, move R left
if it is equal, done

Every step discards one element for good. Why is that safe? If the sum is too big, a[R] plus even the smallest remaining partner is too big, so a[R] can never be part of an answer.

The pointers only move toward each other, so the scan takes at most n steps: O(n). The same pattern merges two sorted lists and removes duplicates in place.

03Sliding window

A sliding window is two pointers moving in the same direction, l and r, marking a contiguous stretch a[l..r]. Keep a running value (like the sum) and update it as the edges move:

expand: move r right and add a[r]
shrink: while the window is "too much" (sum ≥ target), record the answer and move l right, subtracting a[l]

That finds, for example, the shortest subarray with sum ≥ S, or the longest substring without repeated characters (with a set or counts as the window state).

Both pointers only move forward, each at most n times, so the whole thing is O(n) even though there is a loop inside a loop.

04When each trick applies

These tricks need a specific structure, so check it before you use them:

Prefix sums need an operation you can undo: sums (subtract), XOR (XOR again), counts. They do not work for min or max of a range. They also need a static array: if values change between queries, you need a Fenwick or segment tree.
Two pointers from both ends need sorted data, so the "too small / too big" decision is valid.
Sliding window needs monotonicity: growing the window must only increase the sum. With negative numbers that breaks. Then use prefix sums plus a hash map: count subarrays with sum k by looking up p[r+1] − k among earlier prefixes.

A useful signal: "subarray", "substring" or "pair" in the problem plus n up to 10⁵ or more.

Cost at a glance

Build prefix sumsO(n)

Range sum queryO(1)

Two pointers (sorted pair)O(n)

Sliding windowO(n)

Remember

With p[i+1] = p[i] + a[i], any range sum is p[r+1] − p[l] in O(1).
Two pointers work because each move safely rules out one element forever.
A sliding window is O(n) because l and r only move forward, but it needs non-negative values.

Play

Step through the algorithm, then try it on your own input.

👀 What to watch: First watch prefix[] fill left to right, then see each range query use just two cells. In the window phase, notice that l never moves backwards.

Interactive visualizerfocus here, then space ← →

Prefix sums & two pointers

i	0	1	2	3	4	5	6	7	8
a[]		3	1	4	1	5	9	2	6
prefix[]	0	·	·	·	·	·	·	·	·

Prefix sums precompute cumulative totals so any range sum becomes one subtraction.

Pseudocode

 1 prefix[0] = 0 2 prefix[i+1] = prefix[i] + a[i]        // O(n) once 3 sum(l..r) = prefix[r+1] - prefix[l]   // O(1) each 4 // two pointers: shortest window with sum >= target 5 expand r, adding a[r] to the window sum 6 while sum >= target: record length, shrink from l

1 / 1

Check

Three questions. Pick an answer to see why.

a = [2, 5, 1, 4]. The prefix array is p = [0, 2, 7, 8, 12]. What is sum(a[1..3])?

Sorted array [1, 4, 6, 9, 12], target 15. L points to 1, R to 12 (sum 13). What happens next?

Count subarrays with sum exactly k when the array contains negative numbers. Which approach is correct?

Practice

Real problems to lock it in, easiest first.

CSESStatic Range Sum Queries beginner↗LeetCodeTwo Sum II - Input Array Is Sorted intermediate↗LeetCodeMinimum Size Subarray Sum intermediate↗CSESSubarray Sums I intermediate↗LeetCodeSubarray Sum Equals K intermediate↗