Problem 42.9 · Pattern Recognition DrillsMedium

Range Addition

What it teaches:

Practise it on judges as “Range Addition”.

In plain words

Adding to every cell of a range, one cell at a time, is slow when ranges are long. Instead leave two notes: "start adding inc here" at the start, and "stop adding inc here" just after the end. After all updates, walk left to right with a running total of the notes; the running total at each cell is its final value.

Return the final array. Example: length = 5, updates = [[1,3,2],[2,4,3],[0,2,-2]] → [-2, 0, 3, 5, 3].

The problem

Start with an array of zeros of the given length. Each update [start, end, inc] adds inc to every index in [start, end]. Return the final array.

Example 1

Input: length = 5, updates = [[1,3,2],[2,4,3],[0,2,-2]]
Output: [-2, 0, 3, 5, 3]

Constraints

1 ≤ length ≤ 10⁵
Up to 10⁴ updates

Pattern clues in the wording

→ Many range updates
→ Only the final state is read

Stuck? Take one hint at a time

Solution · starter

class Solution {
    public int[] getModifiedArray(int length, int[][] updates) {
        return new int[length];
    }
}

Write your solution locally or in your editor for now. Pick Java, Python, C++, JavaScript or Go above: every solution on this page switches with it. The in-browser runner will run these tests right here.

Test cases

#	Input	Expected
1	length = 5 updates = [[1,3,2],[2,4,3],[0,2,-2]]	[-2,0,3,5,3]

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Difference array · O(length + updates)

Difference array

Time O(length + updates) Space O(length)

diff[start] += inc; diff[end + 1] −= inc; then running sum.

▶ Dry run: Start and stop notes, then a running totallength = 5, updates = [[1,3,2],[2,4,3],[0,2,-2]]

-2

Step 1/4Update [1,3,+2]: +2 at index 1, −2 at index 4 (just after the end). diff has one extra slot for the stop notes.

Approach 1

class Solution {
    public int[] getModifiedArray(int length, int[][] updates) {
        int[] diff = new int[length + 1];
        for (int[] u : updates) { diff[u[0]] += u[2]; diff[u[1] + 1] -= u[2]; }
        int[] out = new int[length];
        for (int i = 0, run = 0; i < length; i++) { run += diff[i]; out[i] = run; }
        return out;
    }
}

Verdict: Applying each update directly is O(length × updates).

Before you submit

Edge cases and common mistakes

Test these inputs

Update covering the whole array
No updates

Mistakes people make

Forgetting the extra slot for end + 1.

Interview

Follow-up questions

What if reads and updates are interleaved?

Command Palette

The problem

Approaches

Difference array

Edge cases and common mistakes

Follow-up questions