Forge Learn/Array & String Techniques

Browsing as a guest. Sign in to save your progress and earn XP as you complete chapters.

Prefix Sums & In-Place Array Tricks

4 min read

You'll learn to

-Precompute prefix sums so any range sum is one subtraction
-Count the work saved across many queries, and know when the preprocessing pays for itself
-Rotate an array in place with three reversals, using no second array

This final chapter before the tier's boss level pulls together two more techniques worth having ready, both built on ideas that have recurred across this tier: precomputation, and true in-place mutation.

An Analogy: The Odometer

A car's odometer shows total distance driven. To know how far you drove between two fuel stops, you do not re-add every trip. You subtract the odometer reading at the first stop from the reading at the second. A prefix sum array is an odometer for your data: running totals, so any stretch is one subtraction.

Prefix Sums: Trade O(n) Preprocessing for O(1) Queries

Given a fixed array and many range-sum queries ("what is the sum from index i to j?"), recomputing sum(items[i:j+1]) for every query costs O(n) per query. That is fine once and expensive across many repeats. A prefix sum array fixes this by precomputing, once, a running total where prefix[i] holds the sum of every element before index i, with prefix[0] = 0 by convention. Any inclusive range sum from i to j then becomes a single subtraction: prefix[j + 1] - prefix[i].

Press Run: build the prefix array once, then answer a range sum with one subtraction

def build_prefix_sums(items):
    prefix = [0] * (len(items) + 1)
    for i, value in enumerate(items):
        prefix[i + 1] = prefix[i] + value
    return prefix

def range_sum(prefix, i, j):
    # inclusive sum of items[i..j]
    return prefix[j + 1] - prefix[i]

items = [2, 4, 6, 8, 10]
prefix = build_prefix_sums(items)
print("prefix array:", prefix)
print("range_sum(1, 3) =", range_sum(prefix, 1, 3), "| directly: items[1] + items[2] + items[3] =", sum(items[1:4]))

n, queries = 10000, 1000
print("direct sums: about", n // 2 * queries, "additions for", queries, "queries covering half the array each")
print("prefix sums:", n, "additions once, then", queries, "subtractions =", n + queries)

For items = [2, 4, 6, 8, 10], the prefix array is [0, 2, 6, 12, 20, 30]. range_sum(prefix, 1, 3) asks for items[1] + items[2] + items[3], which is 4 + 6 + 8 = 18. And prefix[4] - prefix[1] = 20 - 2 = 18 confirms it, in O(1), however wide the range. For 1,000 queries over a 10,000-item array, that is the difference between millions of additions and about eleven thousand operations.

Range-sum query cost comparison

O(n) per query

Recompute each range sum directly

O(1) per query

Prefix sums (after O(n) one-time build)

This is the same "pay once up front, save on every repeated question afterward" trade seen twice already this tier: a hashmap's O(1) lookups after building the table, and memoization's cached subproblem answers.

In-Place Array Tricks

In place means transforming an array using only the O(1) extra space of a few index or temporary variables, with no second array, the same discipline as the in-place reversal earlier in this module. Rotating an array by k positions is a good second example. Instead of building a new rotated list, the classic in-place approach reverses the whole array, then reverses each of the two resulting pieces separately.

Press Run: three reversals rotate [1..7] right by 3, with no extra array

def reverse_range(items, start, end):
    while start < end:
        items[start], items[end] = items[end], items[start]
        start += 1
        end -= 1

def rotate_in_place(items, k):
    n = len(items)
    k %= n
    reverse_range(items, 0, n - 1)     # reverse everything
    reverse_range(items, 0, k - 1)      # reverse the first k (now correctly ordered)
    reverse_range(items, k, n - 1)      # reverse the rest
    return items

print(rotate_in_place([1, 2, 3, 4, 5, 6, 7], 3))
print("steps: reverse all -> [7, 6, 5, 4, 3, 2, 1]; reverse first 3 -> [5, 6, 7, 4, 3, 2, 1]; reverse the rest -> [5, 6, 7, 1, 2, 3, 4]")

Trace it: reversing everything gives [7, 6, 5, 4, 3, 2, 1]. Reversing the first k = 3 elements gives [5, 6, 7, 4, 3, 2, 1]. Reversing the remaining elements gives [5, 6, 7, 1, 2, 3, 4], the original array rotated right by 3, with three O(n) passes and no extra arrays allocated.

Array rotation cost comparison

O(n) time, O(n) space

Build a new rotated list with slicing

O(n) time, O(1) space

Triple in-place reversal

Interview Signal is part of Pro

See a real weak answer next to a real strong one for this exact topic.

Quiz is part of Pro

Test what you just read with a short quiz, and bank the XP.

Ready to Build This?

Level 9: Two Pointers & Sliding Window asks you to solve classic two-pointer and sliding-window array problems, exactly the two_sum_sorted, max_sum_subarray, and variable-window patterns walked through across this module.

Sliding Window Composing Data Structures Into One System

Discussion0

Join the Discussion

No comments yet. Be the first to start the thread!