You are given an integer length and an array updates where updates[i] = [startIdxi, endIdxi, inci].
You have an array arr of length length with all zeros, and you have some operation to apply on arr. In the ith operation, you should increment all the elements arr[startIdxi], arr[startIdxi + 1], ..., arr[endIdxi] by inci.
Return arr after applying all the updates.
Example 1:
Input: length = 5, updates = [[1,3,2],[2,4,3],[0,2,-2]] Output: [-2,0,3,5,3]
Example 2:
Input: length = 10, updates = [[2,4,6],[5,6,8],[1,9,-4]] Output: [0,-4,2,2,2,4,4,-4,-4,-4]
Constraints:
1 <= length <= 1050 <= updates.length <= 1040 <= startIdxi <= endIdxi < length-1000 <= inci <= 1000Problem Overview: You start with an array of length n filled with zeros. Each update specifies [startIndex, endIndex, increment], meaning every element in that range should increase by increment. After applying all updates, return the final array.
Approach 1: Brute Force Range Updates (O(n * k) time, O(1) space)
The direct approach applies every update immediately. For each operation, iterate from startIndex to endIndex and add the increment to each element. If there are k updates and the array length is n, worst‑case complexity becomes O(n * k). This method is easy to implement but performs poorly when ranges are large or updates are frequent.
Approach 2: Difference Array + Prefix Sum (O(n + k) time, O(n) space)
The key insight is that range updates can be represented using a difference array. Instead of modifying every element in the range, add increment at startIndex and subtract increment at endIndex + 1. After processing all updates, compute a running prefix sum across the array to reconstruct the final values. Each update becomes an O(1) operation, and the final pass is O(n). This technique is common in array manipulation problems and closely related to prefix sum patterns.
Approach 3: Binary Indexed Tree + Difference Array (O((n + k) log n) time, O(n) space)
A Binary Indexed Tree (Fenwick Tree) can support range updates and prefix queries efficiently. Combine it with the difference array idea: treat each update as two point modifications in the BIT, then compute prefix sums to recover the final array. Each update costs O(log n), and each prefix query also costs O(log n). This approach is useful when the problem extends to online queries or dynamic updates. It leverages the properties of a Binary Indexed Tree for efficient cumulative operations.
Recommended for interviews: Interviewers typically expect the Difference Array + Prefix Sum solution. It reduces each range update from O(n) to O(1) and demonstrates strong understanding of prefix-based transformations. Mentioning the brute force approach shows baseline reasoning, but implementing the difference array solution signals solid algorithmic optimization skills.
This is a template problem for difference arrays.
We define d as the difference array. To add c to each number in the interval [l,..r], we set d[l] += c and d[r+1] -= c. Finally, we compute the prefix sum of the difference array to obtain the original array.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the array.
Java
C++
Go
TypeScript
JavaScript
The time complexity is O(n times log n).
A Binary Indexed Tree (BIT), also known as a Fenwick Tree, can efficiently perform the following two operations:
update(x, delta): Add a value delta to the number at position x in the sequence.query(x): Query the sum of the interval [1, ... , x] in the sequence, i.e., the prefix sum up to position x.The time complexity for both operations is O(log n).
Java
C++
Go
TypeScript
JavaScript
| Approach | Complexity |
|---|---|
| Difference Array | — |
| Binary Indexed Tree + Difference Array | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Range Updates | O(n * k) | O(1) | Small arrays or very few updates where simplicity matters more than performance |
| Difference Array + Prefix Sum | O(n + k) | O(n) | Best general solution when applying many range updates offline |
| Binary Indexed Tree + Difference Array | O((n + k) log n) | O(n) | Useful when updates and prefix queries must be handled dynamically |
Range Sum Query 2D - Immutable - Leetcode 304 - Python • NeetCode • 50,535 views views
Watch 9 more video solutions →Practice Range Addition with our built-in code editor and test cases.
Practice on FleetCode