Prefix and suffix passes

When each position needs to know about everything on its left and everything on its right, take two directed passes.

Key idea

Prefix sums

Precompute a running total, and the sum of any range becomes a subtraction. This is one of the most reusable ideas in the course.

Build an array where prefix[i] holds the sum of the first i elements. Note the length: n + 1, with a leading zero. That zero is what removes the special case at the start.

1def prefix_sums(nums):2    prefix = [0]3    for value in nums:4        prefix.append(prefix[-1] + value)5    return prefix6 7p = prefix_sums([3, 1, 4, 1, 5])8print(p)9print(p[3] - p[1])      # sum of indices 1..2, which is 1 + 4

Running values also work in the other direction

Nothing says the sweep has to go left to right. A backward sweep gives you, at each position, a summary of everything to its right. Two sweeps give you both sides.

Here is the shape, using running maxima rather than sums so that the mechanism is visible on its own.

1def max_on_each_side(nums):2    n = len(nums)3    left = [None] * n            # largest value strictly to the left of i4    right = [None] * n           # largest value strictly to the right of i5 6    running = None7    for i in range(n):8        left[i] = running9        if running is None or nums[i] > running:10            running = nums[i]11 12    running = None13    for i in range(n - 1, -1, -1):14        right[i] = running15        if running is None or nums[i] > running:16            running = nums[i]17 18    return left, right19 20print(max_on_each_side([3, 1, 4, 2]))

Code lab· 16 min

Prefix sums

Build the general tool before using the specific one. prefix_sums returns an array of length n+1 where position i is the sum of the first i elements, so it starts with 0. range_sum uses it to answer the sum from index i to j inclusive in constant time. count_ranges_equal counts how many ranges in the given list of (i, j) pairs sum to the target.

solution.py

Tests

p = prefix_sums([1, 2, 3, 4, 5])print(p)print(range_sum(p, 0, 4), range_sum(p, 1, 3), range_sum(p, 2, 2))print(count_ranges_equal([1, 2, 3, 4, 5], [(0, 1), (1, 2), (0, 4), (3, 3), (4, 4)], 5))print(prefix_sums([]))

Output

Run tests to see output.

Problem· 20 min

Product Of Array Except Self

Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.

Running values also work in the other direction

Nothing says the sweep has to go left to right. A backward sweep gives you, at each position, a summary of everything to its right. Two sweeps give you both sides.

Here is the shape, using running maxima rather than sums so that the mechanism is visible on its own.

1def max_on_each_side(nums):2    n = len(nums)3    left = [None] * n            # largest value strictly to the left of i4    right = [None] * n           # largest value strictly to the right of i5 6    running = None7    for i in range(n):8        left[i] = running9        if running is None or nums[i] > running:10            running = nums[i]11 12    running = None13    for i in range(n - 1, -1, -1):14        right[i] = running15        if running is None or nums[i] > running:16            running = nums[i]17 18    return left, right19 20print(max_on_each_side([3, 1, 4, 2]))

p = prefix_sums([1, 2, 3, 4, 5])print(p)print(range_sum(p, 0, 4), range_sum(p, 1, 3), range_sum(p, 2, 2))print(count_ranges_equal([1, 2, 3, 4, 5], [(0, 1), (1, 2), (0, 4), (3, 3), (4, 4)], 5))print(prefix_sums([]))