← Create New Paste

Difference Arrays: The Range-Update Trick Interviewers Love

3 views
A surprising number of coding interview problems boil down to the same shape: you are given an array (or a timeline) and a long list of operations of the form "add v to every element from index l to index r", and at the end you need the final values, or the maximum, or a count. The brute-force answer loops over every range and touches every element, which is O(n * q). With n and q both around 10^5 that is ten billion steps. The difference array turns it into O(n + q), and once you see it, you will spot it everywhere. The core idea Instead of storing the values themselves, store how each value differs from the one before it. Let diff[i] = a[i] - a[i-1]. Adding v to the whole range [l, r] only changes two differences: diff[l] goes up by v, and diff[r+1] goes down by v. Every element in between keeps the same difference from its neighbor. So each update is two O(1) writes. When all updates are done, a single prefix-sum pass rebuilds the real array. diff = [0] * (n + 1) for l, r, v in updates: diff[l] += v diff[r + 1] -= v running = 0 for i in range(n): running += diff[i] a[i] = running Where it shows up in interviews - Corporate Flight Bookings (LeetCode 1109): each booking adds seats to a range of flights. Textbook difference array. - Car Pooling (1094): passengers get on at one stop and off at another; check whether capacity is ever exceeded. Put +p at the pickup, -p at the drop-off, prefix-sum, and compare against capacity. - Meeting rooms / maximum overlap: treat each interval as +1 at start and -1 at end. The peak of the prefix sum is the number of rooms needed. Sorting the events is the coordinate-compressed version of the same trick. - Range Addition (370) and "shifting letters" style string problems, where each operation shifts a substring by some amount modulo 26. Edge cases worth saying out loud Interviewers watch for off-by-one handling. Allocate n + 1 slots so diff[r + 1] never overflows, or guard it with an if. Be explicit about whether intervals are inclusive or half-open; in Car Pooling the passenger leaves at the drop-off point, so the -p goes at index "to", not "to + 1". If coordinates are huge (up to 10^9), say you would sort the event points or use a hash map of deltas instead of a dense array. The 2D extension For rectangle updates on a grid, the same idea uses four corners: +v at (r1, c1), -v at (r1, c2+1), -v at (r2+1, c1), +v at (r2+1, c2+1), followed by a 2D prefix sum. Mentioning this as a follow-up is an easy way to show depth. How to present it A good flow: state the brute force and its cost, notice that updates are many and queries come only at the end, propose the difference array, walk through a three-element example by hand, then code it. If the interviewer adds "now queries are interleaved with updates", that is your cue to move to a Fenwick tree with range-update / point-query, which is really a difference array stored in a BIT. Practicing out loud under time pressure is the hard part. If you freeze when the clock is running, Linkjob AI (https://linkjob.ai) can give you real-time help during live job interviews and technical interviews, surfacing hints and structure while you talk through problems like this one.
Created Nov 15, 2026 10:02 Expires Nov 15, 2027 10:02