skip to content

In a difference array of length n, what breaks when a range update ends at the last index?

level: middleimportance: should knowfreq 55%

answer

  1. where does the closing mark actually land
  2. count the distinct positions a mark can occupy
  3. the mark cancels something after the range
  4. what is there to cancel past the last index
  5. one spare slot, or one guard

basics

~20 s

The closing write lands at index r+1, which equals n when the range ends at the last position — one slot past the array. Fix it by sizing the difference array n+1 and ignoring the extra slot, or by skipping that write when r+1 equals n.

solid answer

~50 s

Every range update makes a closing write at `r+1`, and when `r == n-1` that index is `n`, which is out of bounds for an `n`-length difference array. There are two standard fixes and both are correct. Size the difference array `n+1`, let the stray mark land in the final slot, and simply stop the materialize pass at index `n-1` so the slot is never read. Or guard the write with `if r + 1 < n`. Skipping is safe precisely because that mark's only job is to cancel the increment *after* the range, and there is nothing after the last index to cancel. The failure mode is nasty in a good way — it crashes loudly on a full-aisle update rather than quietly returning wrong counts, so it usually surfaces on the first realistic test rather than in production.

code

pseudocode · 8 lines
pseudocode
diff = new array of length n, all zeros
for each (l, r, v) in updates:
    diff[l] = diff[l] + v
    diff[r + 1] = diff[r + 1] - v      // fails when r == n-1
running = 0
for i in 0..n-1:
    running = running + diff[i]
    counts[i] = counts[i] + running

go deeper

for a junior

Remember that the closing mark goes one position past the range end, so an update touching the last index needs either a spare slot or a guard.

for a middle

Explain that marks occupy an index space one wider than values, and justify why skipping the final mark loses nothing at all.

for a senior

Show that you reach for the boundary test first — a single-element update at the last index — and reject clamping because it trades a crash for silent corruption.

for a principal

Frame it as an API contract question: decide whether ranges are half-open or inclusive once, document it, and let that choice remove the whole class of endpoint bugs from the codebase.

## Where the extra index comes from A difference array encodes a range increment on `l..r` as two marks: `+v` at `l`, which starts a suffix increment, and `-v` at `r+1`, which cancels it. The cancelling mark is deliberately *outside* the range — that is what makes the arithmetic exact. So the index space the marks live in is one wider than the value space: valid mark positions run `0..n`, while valid value positions run `0..n-1`. When a caller submits an update that runs to the end of the array — a stock adjustment applied to every shelf position from some point to the end of the aisle — `r` is `n-1` and the closing mark wants index `n`. On an `n`-length difference array that write is out of bounds. ## Both fixes, and why each is correct **Fix one: allocate `n+1`.** Give the difference array one spare slot. The stray mark lands in `diff[n]` and is simply never read, because the materialize loop runs `i in 0..n-1`. This costs one extra slot of memory, keeps the update code branch-free, and makes the update path uniform for every possible `r`. It is the version to prefer when updates are hot and you want no per-update conditional. **Fix two: guard the write.** Keep the array at length `n` and write the closing mark only when `r + 1 < n`. This is correct for the same reason the spare slot works: the mark exists purely to cancel the increment for indices *after* `r`, and when `r` is the last index there are no such indices. Dropping the cancellation loses nothing. What is *not* a fix is clamping — writing the closing mark at `min(r+1, n-1)`. That silently subtracts `v` from the last element, so a range that should have raised the final shelf count instead leaves it unchanged or lowers it. Clamping converts a loud crash into a quiet wrong answer, which is strictly worse. ## Tracing the boundary by hand Take `n = 4`, all counts zero, and one update: add 5 to positions `1..3`. With an `n+1`-sized difference array the marks are `diff = [0, +5, 0, 0, -5]`, where the `-5` sits in the spare slot. The materialize pass carries `running`: at `i=0` it is 0, at `i=1` it becomes 5, and it stays 5 through `i=3`. Output `[0, 5, 5, 5]` — correct, and the `-5` was never touched. With the guard, `diff = [0, +5, 0, 0]` and the pass produces the same `[0, 5, 5, 5]`. The two fixes are observationally identical on the value range. Now contrast the clamped version: `diff = [0, +5, 0, -5]`, and the pass yields `[0, 5, 5, 0]`. The last position lost its update entirely. Nothing crashes; the counts are just wrong. ## The neighbouring off-by-one The boundary bug has a sibling that is easier to miss: closing at `r` instead of `r+1`. That version never goes out of bounds, so it never crashes — it just drops the increment on the range's final element every single time. Small hand-built tests with wide ranges can still look plausible if you only spot-check the middle. The test that catches both bugs in one shot is a single-element range where `l == r == n-1`: a correct implementation increments exactly that one position, the `r`-closing bug increments nothing, and the unguarded version crashes. ## What an interviewer is watching for This is a small detail, but it is the detail that separates a candidate who has actually run the pattern from one who has read about it. Two things read well. First, stating the invariant out loud — *marks live in an index space one wider than values* — rather than patching a symptom. Second, choosing between the spare slot and the guard on a stated reason (branch-free hot path versus not allocating an odd-sized array) instead of shrugging. Third, and best, naming the single-element-at-the-end test case unprompted, because that shows the habit of testing at the boundary rather than in the comfortable middle.

  • Why is clamping the closing write to index n-1 a worse fix than skipping it?
    Clamping actually writes `-v` at the last valid index, so the running sum drops there and the final position silently misses its increment. Skipping writes nothing, which is correct because the mark only cancels indices *after* the range and none exist. Clamping turns a crash into wrong output — a bug that survives to production instead of failing the first full-range test.
  • What single test case catches both the out-of-bounds bug and the close-at-r bug?
    A one-element update at the very end: `l == r == n-1`. A correct implementation raises exactly that position. The unguarded version indexes past the array and crashes. The version that closes at `r` instead of `r+1` cancels its own increment immediately and leaves the position unchanged. One assertion, both bugs.
  • Does the spare slot change the space complexity of the approach?
    No. One extra slot is O(1) additional space on top of the O(n) difference array, so the asymptotic cost is unchanged. It is a constant, not a factor. The only reason to prefer the guard is stylistic — avoiding an array whose length does not match the data it describes — not a memory argument.

saying these in an interview costs you the question

  • Clamps the closing write to the last valid index
  • Says the boundary case cannot happen in practice
  • Only tests ranges that sit in the middle of the array
  • Claims the spare slot costs meaningful extra memory
  • Cannot say why dropping the final mark is safe

context

resolving links…