Loading…

mediumArraysFrequently asked

Array Manipulation

Q: How do you solve Array Manipulation using the Brute Force — Apply Every Operation Cell by Cell approach?

When to use it: Open with it to define the problem precisely, then immediately flag the O(n·m) cost as the reason to switch. Allocate the zero array and, for every operation, add `k` to each element in `[a, b]` directly. **Why it's the obvious first move.** The problem statement literally says 'add k to every element from a to b'. Translating that word-for-word gives a double loop: outer over operations, inner over the range. It's correct and easy to reason about. **Why it collapses at scale.** A single operation with `a = 1, b = n` writes `n` cells. With `m` such operations you do `n·m` writes — for the given limits that's around two trillion. Even at a billion simple operations per second, that's minutes, not milliseconds. The waste is *overlap*: cells covered by many ranges get rewritten over and over. **The realization that unlocks the optimal.** We don't need the value of every cell *while* we work — only the final maximum. That means we can record each operation cheaply and reconstruct values in a single pass at the end. That reconstruction is the difference array. Time complexity: O(n·m). Space complexity: O(n).

Q: How do you solve Array Manipulation using the Difference Array + Prefix Sum (Optimal) approach?

When to use it: The intended answer. Frame it as 'store the change at the boundaries, integrate once'. Keep a `diff` array where `diff[i]` stores the *change* in value entering index `i` rather than the value itself. A range-add `[a, b, k]` is recorded as just two edits, then a single prefix sum turns differences back into values. **Why two edits capture a whole range.** Think of the value array as a function and `diff` as its derivative. Adding `k` across `[a, b]` is a step up of `k` at `a` and a step back down of `k` immediately after `b`. So we set `diff[a] += k` and `diff[b + 1] -= k`. The interior of the range needs no edits — once you integrate (prefix-sum), every index from `a` through `b` inherits the `+k`, and at `b + 1` the `−k` cancels it. That's why each operation is O(1) regardless of how wide its range is. **Why the b+1 guard and size n+2.** When `b == n`, the index `b + 1 == n + 1` must exist so the subtraction doesn't crash or, worse, silently wrap. Sizing the array `n + 2` (1-based) guarantees `diff[b + 1]` is always a legal slot; we simply ignore that extra cell during the final scan. **Why the max appears during the sweep.** Reconstructing values means `value[i] = diff[1] + diff[2] + … + diff[i]` — a running prefix sum. The peak can occur at any index, so we compare against `best` *as we accumulate*, never needing to store the full value array. This is also why we only need O(1) beyond the diff array to find the answer. **Why 64-bit matters.** Up to 2×10⁵ overlapping operations each adding as much as 10⁹ can push the running sum past 2³¹. In Java the accumulator and diff entries must be `long`; Python integers are arbitrary precision, so no special handling. Time complexity: O(n + m). Space complexity: O(n).

Arrays & Hashing · 43 of 83 · 9 min

Start with a 1-indexed array of n zeros. You're given m operations; each is a triple [a, b, k] meaning add `k` to every element from index `a` to index `b` inclusive. After performing all m operations, return the maximum value in the array.

In plain English

You apply m additive updates to ranges of a big zero array and only care about the single largest final value. Because all updates are known ahead of time and order is irrelevant for the final state, you can defer the work: record each range as a +k/−k delta pair, then sweep once to find the peak.

Examples

Example 1

Input: n = 5, ops = [[1,2,100],[2,5,100],[3,4,100]]
Output: 200
Note: Final array is [100, 200, 200, 200, 100]; index 2 reaches 200 where the first two ranges overlap.

Example 2

Input: n = 10, ops = [[1,5,3],[4,8,7],[6,9,1]]
Output: 10
Note: Indices 4 and 5 get 3+7 = 10, the overlap of the first two ranges.

Constraints

3 ≤ n ≤ 10⁷
1 ≤ m ≤ 2 × 10⁵
1 ≤ a ≤ b ≤ n
0 ≤ k ≤ 10⁹

Clarifying questions4First question: Are indices 1-based?Explore questions

Q1.Are indices 1-based?
Yes for the classic problem. Size the diff array n+2 so b+1 is valid when b equals n.
Q2.Do I need every final value or just the maximum?
Just the maximum. That lets you track a running sum and never store the full array.
Q3.Can the values overflow 32 bits?
Yes. With k up to 10⁹ and many overlapping ranges, the peak can exceed 2³¹. Use a 64-bit accumulator in Java.
Q4.Are operations applied in order or can I reorder them?
Addition is commutative, so order doesn't affect the final array — that's exactly why the offline difference-array trick is valid.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

You apply m range-add operations [a, b, k] to a zero-filled array of length n, then return the maximum final value. Don't touch every cell in every range — that's O(n·m). Use a difference array: add k at index a and subtract k just past b (at b+1). One prefix-sum sweep at the end reconstructs running values; track the max as you go. Total O(n + m).

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you recognize that overlapping range additions don't need per-cell updates, and can express a range op as two boundary deltas reconstructed by a prefix sum. Also whether you anticipate 64-bit overflow.

Where candidates slip

Looping a[j] += k for j in [a, b] — correct but O(n·m), times out at n = 10⁷, m = 2×10⁵. Or forgetting the b+1 guard and writing out of bounds when b == n.

How to stand out

Call it a difference array and explain the calculus intuition: you're storing the derivative and integrating once. Mention you never even need to materialize the full array — a single running sum tracks the max.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Apply Every Operation Cell by Cell	`O(n·m)`	`O(n)`	Open with it to define the problem precisely, then immediately flag the O(n·m) cost as the reason to switch.	Read
2	Difference Array + Prefix Sum (Optimal)Optimal	`O(n + m)`	`O(n)`	The intended answer. Frame it as 'store the change at the boundaries, integrate once'.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.Explore the full tree

Range-add as two boundary deltas

How to read it:Each operation touches only two indices; the prefix sum reconstructs the rest.

Rendering diagram…

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Brute Force — Apply Every Operation Cell by Cell

TimeO(n·m)SpaceO(n)

Open with it to define the problem precisely, then immediately flag the O(n·m) cost as the reason to switch.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The literal reading: for each operation, walk every index from a to b and add k. What's the worst-case total work?

2Hint 2Explore hint

With n up to 10⁷ and m up to 2×10⁵, a single operation can touch the whole array. How many cell writes is that across all operations?

3Hint 3Explore hint

You re-touch overlapping cells repeatedly. Is there a way to record an operation in constant time and reconstruct values later?

A · Core idea

Allocate the zero array and, for every operation, add k to each element in [a, b] directly.

Why it's the obvious first move. The problem statement literally says 'add k to every element from a to b'. Translating that word-for-word gives a double loop: outer over operations, inner over the range. It's correct and easy to reason about.

Why it collapses at scale. A single operation with a = 1, b = n writes n cells. With m such operations you do n·m writes — for the given limits that's around two trillion. Even at a billion simple operations per second, that's minutes, not milliseconds. The waste is overlap: cells covered by many ranges get rewritten over and over.

The realization that unlocks the optimal. We don't need the value of every cell while we work — only the final maximum. That means we can record each operation cheaply and reconstruct values in a single pass at the end. That reconstruction is the difference array.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

n = 5, ops = [[1,2,100],[2,5,100],[3,4,100]]

Array state

after op 1

indices 1..2 += 100

100

[0]

100

[1]

[2]

[3]

[4]

Current pointerResolved stateNot processed

Final result200

C · Code with teaching comments

Reference implementation previewpublic long arrayManipulation(int n, int[][] ops) { long[] arr = new long[n + 1]; for (int[] op : ops) { int a = op[0], b = op[1], k = op[2]; for (int i = a; i <= b; i++) {Explore the full code

solution.javaJava

Brute Force — Apply Every Operation Cell by Cell — reference

2 teaching notes

1
public long arrayManipulation(int n, int[][] ops) {
2
    long[] arr = new long[n + 1];
3
    for (int[] op : ops) {
4
        int a = op[0], b = op[1], k = op[2];
5
        // Touches every cell in the range — the inner loop that makes this O(n·m).
6
        for (int i = a; i <= b; i++) {
7
            arr[i] += k;
8
        }
9
    }
10
    long best = 0;
11
    for (int i = 1; i <= n; i++) {
12
        // Final scan for the maximum after all writes.
13
        best = Math.max(best, arr[i]);
14
    }
15
    return best;
16
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.16 lines

D · Why it works and complexityO(n·m) timeO(n) spaceOpen the invariant and proofExplore the proof

The brute force re-touches overlapping cells. The fix isn't a faster loop — it's recording each range as a boundary event so overlaps cost nothing extra.

ComplexityO(n·m) time, O(n) space — Each operation can span the entire array (b − a + 1 up to n), and there are m operations: up to n·m ≈ 2×10¹² writes. Far too slow.

E · Edge cases and pitfalls5all ops cover the whole array — Every cell ends equal; the brute force does the maximum n·m work.Explore edge cases

Edge cases handled

all ops cover the whole arrayEvery cell ends equal; the brute force does the maximum n·m work.
single op [1, n, k]Returns k; brute force still writes all n cells.

Pitfalls

Assuming it passes — it TLEs at n = 10⁷, m = 2×10⁵.
Using int for the array in Java — overlapping k values overflow 32 bits.
Off-by-one on the inclusive upper bound b.

03.2

Approach 2 of 2 · Optimal

Difference Array + Prefix Sum (Optimal)

TimeO(n + m)SpaceO(n)

The intended answer. Frame it as 'store the change at the boundaries, integrate once'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Instead of marking every cell a range covers, can you mark just where the range's effect *begins* and where it *ends*?

2Hint 2Explore hint

Add k at index a (effect starts) and subtract k at index b+1 (effect ends). What operation turns these boundary marks back into actual values?

3Hint 3Explore hint

A prefix sum over the boundary marks reconstructs each cell's value. Track the maximum during that single sweep.

A · Core idea

Keep a diff array where diff[i] stores the change in value entering index i rather than the value itself. A range-add [a, b, k] is recorded as just two edits, then a single prefix sum turns differences back into values.

Why two edits capture a whole range. Think of the value array as a function and diff as its derivative. Adding k across [a, b] is a step up of k at a and a step back down of k immediately after b. So we set diff[a] += k and diff[b + 1] -= k. The interior of the range needs no edits — once you integrate (prefix-sum), every index from a through b inherits the +k, and at b + 1 the −k cancels it. That's why each operation is O(1) regardless of how wide its range is.

Why the b+1 guard and size n+2. When b == n, the index b + 1 == n + 1 must exist so the subtraction doesn't crash or, worse, silently wrap. Sizing the array n + 2 (1-based) guarantees diff[b + 1] is always a legal slot; we simply ignore that extra cell during the final scan.

Why the max appears during the sweep. Reconstructing values means value[i] = diff[1] + diff[2] + … + diff[i] — a running prefix sum. The peak can occur at any index, so we compare against best as we accumulate, never needing to store the full value array. This is also why we only need O(1) beyond the diff array to find the answer.

Why 64-bit matters. Up to 2×10⁵ overlapping operations each adding as much as 10⁹ can push the running sum past 2³¹. In Java the accumulator and diff entries must be long; Python integers are arbitrary precision, so no special handling.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

n = 5, ops = [[1,2,100],[2,5,100],[3,4,100]]

Array state

i=1

running = 0 + 100 = 100

100

[0]

Current pointerResolved stateNot processed

Final result200

C · Code with teaching comments

solution.javaJava

Difference Array + Prefix Sum (Optimal) — optimal

4 teaching notes

1
public long arrayManipulation(int n, int[][] ops) {
2
    // Size n+2 so diff[b+1] is valid even when b == n; long avoids 32-bit overflow.
3
    long[] diff = new long[n + 2];
4
    for (int[] op : ops) {
5
        int a = op[0], b = op[1], k = op[2];
6
        // Step the derivative up by k where the range begins.
7
        diff[a] += k;
8
        // Step it back down just past the range end so the +k cancels there.
9
        diff[b + 1] -= k;
10
    }
11
    long running = 0, best = 0;
12
    for (int i = 1; i <= n; i++) {
13
        // Prefix sum: integrate the derivative to recover the actual value at i.
14
        running += diff[i];
15
        best = Math.max(best, running);
16
    }
17
    return best;
18
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.18 lines

D · Why it works and complexityO(n + m) timeO(n) spaceOpen the invariant and proofExplore the proof

Range-add then query is the discrete analog of integrate-the-derivative. Storing changes at boundaries makes each update O(1) no matter how wide the range; one integration pass recovers everything. This same pattern powers 2D versions (image integral / submatrix sums) and interval-booking problems.

ComplexityO(n + m) time, O(n) space — m operations × O(1) per boundary update = O(m). One prefix-sum sweep over n+1 entries = O(n). Total O(n + m), with O(n) space for the diff array.

E · Edge cases and pitfalls5op with a == b — diff[a] += k and diff[a+1] -= k; the single cell gets exactly k.Explore edge cases

Edge cases handled

op with a == bdiff[a] += k and diff[a+1] -= k; the single cell gets exactly k.
all k = 0Every running sum stays 0; best returns 0.

Pitfalls

Forgetting the n+2 size and crashing on diff[b+1] when b == n.
Using int instead of long in Java — the running sum overflows.
Scanning for the max after building a full value array — wastes O(n) memory you don't need.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic long arrayManipulation(int n, int[][] ops) { long[] diff = new long[n + 2]; for (int[] op : ops) { int a = op[0], b = op[1], k = op[2]; diff[a] += k;Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Per-cell range application

Adding k to every cell of every range is O(n·m); at the given limits it's ~2×10¹² operations and times out.

Explore the code comparison

Don't write this

for (int[] op : ops) {
    for (int i = op[0]; i <= op[1]; i++) {
        arr[i] += op[2];
    }
}

Write this instead

for (int[] op : ops) {
    diff[op[0]] += op[2];
    diff[op[1] + 1] -= op[2];
}

Missing the b+1 boundary slot

When b == n, diff[b+1] is index n+1; an array of size n+1 has no such slot and throws.

Explore the code comparison

Don't write this

long[] diff = new long[n + 1];
// diff[b + 1] -= k;  // throws when b == n

Write this instead

long[] diff = new long[n + 2];
diff[b + 1] -= k;

32-bit overflow

Up to 2×10⁵ additions of 10⁹ can exceed 2³¹; the running max wraps to a wrong, often negative, value.

Explore the code comparison

Don't write this

int running = 0, best = 0;

Write this instead

long running = 0, best = 0;

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Difference array + prefix sum for offline range updates

Code pattern to memorize

diff[a] += k
diff[b + 1] -= k        # guard b+1 ≤ n
# then sweep:
running = 0; best = 0
for i in 1..n: running += diff[i]; best = max(best, running)

Rules to remember

1A range-add [a, b, k] becomes two point updates: +k at a, −k at b + 1 — record the boundaries, not the interior.
2Use 1-based indexing and size the diff array n + 2 so b + 1 is always a valid index even when b == n.
3The maximum appears during the prefix-sum sweep, not after — track best while you accumulate running.
4Values overflow 32-bit: k up to 10⁹ across up to 2×10⁵ operations means use long in Java, plain int is fine in Python.
5This works because all operations are known up front (offline) — you never need an intermediate value mid-stream.

Use this pattern when

Many range-add updates, then a single query (max/sum) at the end
Updates are known in advance (offline), order doesn't matter for the final array
You'd otherwise loop over each range and re-touch overlapping cells

Choose another pattern when

Queries interleaved with updates and you need values mid-stream → Fenwick/BIT or segment tree with lazy propagation
Range updates are multiplicative or assignments, not additions → segment tree with lazy
You need every element's final value individually, not an aggregate → still fine, just do the full sweep

Interview takeaway

A range-add on an array is the derivative trick: store the *change* at the boundaries (`+k` at start, `−k` after end), then integrate once with a prefix sum. m updates in O(m), one sweep in O(n) — O(n + m) total instead of O(n·m).

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternDifference array (the discrete derivative). Record each range-add as +k at the start and −k just past the end, then integrate with one prefix-sum sweep. Turns O(n·m) range updates into O(n + m). Generalizes to 2D submatrix updates and underpins interval-booking sweeps.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Same pattern

←

2D Array - DS

Continue · Next problem

Arrays: DS (Reverse an Array)

mediumArraysFrequently asked

Array Manipulation

Arrays & Hashing · 43 of 83 · 9 min

In plain English

Examples

Example 1

Input: n = 5, ops = [[1,2,100],[2,5,100],[3,4,100]]
Output: 200
Note: Final array is [100, 200, 200, 200, 100]; index 2 reaches 200 where the first two ranges overlap.

Example 2

Input: n = 10, ops = [[1,5,3],[4,8,7],[6,9,1]]
Output: 10
Note: Indices 4 and 5 get 3+7 = 10, the overlap of the first two ranges.

Constraints

3 ≤ n ≤ 10⁷
1 ≤ m ≤ 2 × 10⁵
1 ≤ a ≤ b ≤ n
0 ≤ k ≤ 10⁹

Clarifying questions4First question: Are indices 1-based?Explore questions

Q1.Are indices 1-based?
Yes for the classic problem. Size the diff array n+2 so b+1 is valid when b equals n.
Q2.Do I need every final value or just the maximum?
Just the maximum. That lets you track a running sum and never store the full array.
Q3.Can the values overflow 32 bits?
Yes. With k up to 10⁹ and many overlapping ranges, the peak can exceed 2³¹. Use a 64-bit accumulator in Java.
Q4.Are operations applied in order or can I reorder them?
Addition is commutative, so order doesn't affect the final array — that's exactly why the offline difference-array trick is valid.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Where candidates slip

Looping a[j] += k for j in [a, b] — correct but O(n·m), times out at n = 10⁷, m = 2×10⁵. Or forgetting the b+1 guard and writing out of bounds when b == n.

How to stand out

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Apply Every Operation Cell by Cell	`O(n·m)`	`O(n)`	Open with it to define the problem precisely, then immediately flag the O(n·m) cost as the reason to switch.	Read
2	Difference Array + Prefix Sum (Optimal)Optimal	`O(n + m)`	`O(n)`	The intended answer. Frame it as 'store the change at the boundaries, integrate once'.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.Explore the full tree

Range-add as two boundary deltas

How to read it:Each operation touches only two indices; the prefix sum reconstructs the rest.

Rendering diagram…

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Brute Force — Apply Every Operation Cell by Cell

TimeO(n·m)SpaceO(n)

Open with it to define the problem precisely, then immediately flag the O(n·m) cost as the reason to switch.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The literal reading: for each operation, walk every index from a to b and add k. What's the worst-case total work?

2Hint 2Explore hint

With n up to 10⁷ and m up to 2×10⁵, a single operation can touch the whole array. How many cell writes is that across all operations?

3Hint 3Explore hint

You re-touch overlapping cells repeatedly. Is there a way to record an operation in constant time and reconstruct values later?

A · Core idea

Allocate the zero array and, for every operation, add k to each element in [a, b] directly.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

n = 5, ops = [[1,2,100],[2,5,100],[3,4,100]]

Array state

after op 1

indices 1..2 += 100

100

[0]

100

[1]

[2]

[3]

[4]

Current pointerResolved stateNot processed

Final result200

C · Code with teaching comments

solution.javaJava

Brute Force — Apply Every Operation Cell by Cell — reference

2 teaching notes

1
public long arrayManipulation(int n, int[][] ops) {
2
    long[] arr = new long[n + 1];
3
    for (int[] op : ops) {
4
        int a = op[0], b = op[1], k = op[2];
5
        // Touches every cell in the range — the inner loop that makes this O(n·m).
6
        for (int i = a; i <= b; i++) {
7
            arr[i] += k;
8
        }
9
    }
10
    long best = 0;
11
    for (int i = 1; i <= n; i++) {
12
        // Final scan for the maximum after all writes.
13
        best = Math.max(best, arr[i]);
14
    }
15
    return best;
16
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.16 lines

D · Why it works and complexityO(n·m) timeO(n) spaceOpen the invariant and proofExplore the proof

The brute force re-touches overlapping cells. The fix isn't a faster loop — it's recording each range as a boundary event so overlaps cost nothing extra.

ComplexityO(n·m) time, O(n) space — Each operation can span the entire array (b − a + 1 up to n), and there are m operations: up to n·m ≈ 2×10¹² writes. Far too slow.

E · Edge cases and pitfalls5all ops cover the whole array — Every cell ends equal; the brute force does the maximum n·m work.Explore edge cases

Edge cases handled

all ops cover the whole arrayEvery cell ends equal; the brute force does the maximum n·m work.
single op [1, n, k]Returns k; brute force still writes all n cells.

Pitfalls

Assuming it passes — it TLEs at n = 10⁷, m = 2×10⁵.
Using int for the array in Java — overlapping k values overflow 32 bits.
Off-by-one on the inclusive upper bound b.

03.2

Approach 2 of 2 · Optimal

Difference Array + Prefix Sum (Optimal)

TimeO(n + m)SpaceO(n)

The intended answer. Frame it as 'store the change at the boundaries, integrate once'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Instead of marking every cell a range covers, can you mark just where the range's effect *begins* and where it *ends*?

2Hint 2Explore hint

Add k at index a (effect starts) and subtract k at index b+1 (effect ends). What operation turns these boundary marks back into actual values?

3Hint 3Explore hint

A prefix sum over the boundary marks reconstructs each cell's value. Track the maximum during that single sweep.

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

n = 5, ops = [[1,2,100],[2,5,100],[3,4,100]]

Array state

i=1

running = 0 + 100 = 100

100

[0]

Current pointerResolved stateNot processed

Final result200

C · Code with teaching comments

solution.javaJava

Difference Array + Prefix Sum (Optimal) — optimal

4 teaching notes

1
public long arrayManipulation(int n, int[][] ops) {
2
    // Size n+2 so diff[b+1] is valid even when b == n; long avoids 32-bit overflow.
3
    long[] diff = new long[n + 2];
4
    for (int[] op : ops) {
5
        int a = op[0], b = op[1], k = op[2];
6
        // Step the derivative up by k where the range begins.
7
        diff[a] += k;
8
        // Step it back down just past the range end so the +k cancels there.
9
        diff[b + 1] -= k;
10
    }
11
    long running = 0, best = 0;
12
    for (int i = 1; i <= n; i++) {
13
        // Prefix sum: integrate the derivative to recover the actual value at i.
14
        running += diff[i];
15
        best = Math.max(best, running);
16
    }
17
    return best;
18
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.18 lines

D · Why it works and complexityO(n + m) timeO(n) spaceOpen the invariant and proofExplore the proof

ComplexityO(n + m) time, O(n) space — m operations × O(1) per boundary update = O(m). One prefix-sum sweep over n+1 entries = O(n). Total O(n + m), with O(n) space for the diff array.

E · Edge cases and pitfalls5op with a == b — diff[a] += k and diff[a+1] -= k; the single cell gets exactly k.Explore edge cases

Edge cases handled

op with a == bdiff[a] += k and diff[a+1] -= k; the single cell gets exactly k.
all k = 0Every running sum stays 0; best returns 0.

Pitfalls

Forgetting the n+2 size and crashing on diff[b+1] when b == n.
Using int instead of long in Java — the running sum overflows.
Scanning for the max after building a full value array — wastes O(n) memory you don't need.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic long arrayManipulation(int n, int[][] ops) { long[] diff = new long[n + 2]; for (int[] op : ops) { int a = op[0], b = op[1], k = op[2]; diff[a] += k;Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Per-cell range application

Adding k to every cell of every range is O(n·m); at the given limits it's ~2×10¹² operations and times out.

Explore the code comparison

Don't write this

for (int[] op : ops) {
    for (int i = op[0]; i <= op[1]; i++) {
        arr[i] += op[2];
    }
}

Write this instead

for (int[] op : ops) {
    diff[op[0]] += op[2];
    diff[op[1] + 1] -= op[2];
}

Missing the b+1 boundary slot

When b == n, diff[b+1] is index n+1; an array of size n+1 has no such slot and throws.

Explore the code comparison

Don't write this

long[] diff = new long[n + 1];
// diff[b + 1] -= k;  // throws when b == n

Write this instead

long[] diff = new long[n + 2];
diff[b + 1] -= k;

32-bit overflow

Up to 2×10⁵ additions of 10⁹ can exceed 2³¹; the running max wraps to a wrong, often negative, value.

Explore the code comparison

Don't write this

int running = 0, best = 0;

Write this instead

long running = 0, best = 0;

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Difference array + prefix sum for offline range updates

Code pattern to memorize

diff[a] += k
diff[b + 1] -= k        # guard b+1 ≤ n
# then sweep:
running = 0; best = 0
for i in 1..n: running += diff[i]; best = max(best, running)

Rules to remember

1A range-add [a, b, k] becomes two point updates: +k at a, −k at b + 1 — record the boundaries, not the interior.
2Use 1-based indexing and size the diff array n + 2 so b + 1 is always a valid index even when b == n.
3The maximum appears during the prefix-sum sweep, not after — track best while you accumulate running.
4Values overflow 32-bit: k up to 10⁹ across up to 2×10⁵ operations means use long in Java, plain int is fine in Python.
5This works because all operations are known up front (offline) — you never need an intermediate value mid-stream.

Use this pattern when

Many range-add updates, then a single query (max/sum) at the end
Updates are known in advance (offline), order doesn't matter for the final array
You'd otherwise loop over each range and re-touch overlapping cells

Choose another pattern when

Queries interleaved with updates and you need values mid-stream → Fenwick/BIT or segment tree with lazy propagation
Range updates are multiplicative or assignments, not additions → segment tree with lazy
You need every element's final value individually, not an aggregate → still fine, just do the full sweep

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Same pattern

←

2D Array - DS

Continue · Next problem

Arrays: DS (Reverse an Array)