Arrays and Hashing
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.
Why it works
The subtraction
The sum from index i to j inclusive is prefix[j + 1] - prefix[i]. Everything up to j, minus everything before i, leaves exactly the middle.
That turns range-sum questions from O(n) each into O(1) each, after an O(n) setup. Answering q queries drops from O(q * n) to O(n + q).
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.
Why it works
Why the assignment comes before the update
In each loop, left[i] is written before running absorbs nums[i]. That is what makes it strictly to the left rather than including position i itself. Swap the two lines and every entry silently includes its own element.
State the invariant as you write it: at the top of each iteration, running summarizes everything already passed and nothing else. Almost every bug in this pattern is that sentence being false.
Gotcha
The boundary is the thing to check
The first position has nothing to its left. For sums that means 0, for products it means 1, for a maximum it means there is no answer at all.
Check that boundary before you check anything else. If your first entry is not the identity for whatever you are accumulating, the recurrence is off by one and every later entry is wrong too.
Tip
Two sides, combined
Once you hold a summary of the left and a summary of the right at every position, questions that sounded like they needed nested loops collapse into a single combination step at each index.
That is the move the problem below wants. Work out what the two sides need to be, build them in two sweeps, and combine.
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.
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 the tests when you are ready.
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.