Range Addition solution and explanation
Google
9 more videos on this problem
Range Addition | Arrays & StringsPepcoding · 24:34 · 19K views
Leetcode 370. Range Addition | C++Unofficial Sendoh · 10:28 · 2K views
米开：LeetCode 370. Range AdditionM.C米开朗基罗 · 5:21 · 2K views
LeetCode 370. Range AdditionKacy Codes · 10:56 · 1K views
Leetcode Range Addition | Solving AlgoPrep 151 | Nishant ChaharAlgoPrep · 8:42 · 1K views
370. Range Addition (Leetcode Medium)Programming Live with Larry · 9:22 · 1K views
Introduction to Difference Array | Range update query O(1) | LeetCode 370 Range Addition | GoogleCode Harmony · 16:49 · 1K views
Leetcode 370: Range AdditionVrushali Jadhav · 10:45 · 1K views
370. Range Addition - Week 5/5 Leetcode November ChallengeProgramming Live with Larry · 3:07 · 284 views
Leetcode 370. Range Addition (difference)LetsCode · 9:39 · 249 views
The problem
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 <= 1000
Approach overview
Problem 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.
Approach 1: Difference Array
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.
class Solution:
def getModifiedArray(self, length: int, updates: List[List[int]]) -> List[int]:
d = [0] * length
for l, r, c in updates:
d[l] += c
if r + 1 < length:
d[r + 1] -= c
return list(accumulate(d))class Solution {
public int[] getModifiedArray(int length, int[][] updates) {
int[] d = new int[length];
for (var e : updates) {
int l = e[0], r = e[1], c = e[2];
d[l] += c;
if (r + 1 < length) {
d[r + 1] -= c;
}
}
for (int i = 1; i < length; ++i) {
d[i] += d[i - 1];
}
return d;
}
}class Solution {
public:
vector<int> getModifiedArray(int length, vector<vector<int>>& updates) {
vector<int> d(length);
for (const auto& e : updates) {
int l = e[0], r = e[1], c = e[2];
d[l] += c;
if (r + 1 < length) {
d[r + 1] -= c;
}
}
for (int i = 1; i < length; ++i) {
d[i] += d[i - 1];
}
return d;
}
};/**
* @param {number} length
* @param {number[][]} updates
* @return {number[]}
*/
var getModifiedArray = function (length, updates) {
const d = Array(length).fill(0);
for (const [l, r, c] of updates) {
d[l] += c;
if (r + 1 < length) {
d[r + 1] -= c;
}
}
for (let i = 1; i < length; ++i) {
d[i] += d[i - 1];
}
return d;
};function getModifiedArray(length: number, updates: number[][]): number[] {
const d: number[] = Array(length).fill(0);
for (const [l, r, c] of updates) {
d[l] += c;
if (r + 1 < length) {
d[r + 1] -= c;
}
}
for (let i = 1; i < length; ++i) {
d[i] += d[i - 1];
}
return d;
}func getModifiedArray(length int, updates [][]int) []int {
d := make([]int, length)
for _, e := range updates {
l, r, c := e[0], e[1], e[2]
d[l] += c
if r+1 < length {
d[r+1] -= c
}
}
for i := 1; i < length; i++ {
d[i] += d[i-1]
}
return d
}Approach 2: Binary Indexed Tree + Difference Array
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:
- Point Update
update(x, delta): Add a valuedeltato the number at positionxin the sequence. - Prefix Sum Query
query(x): Query the sum of the interval[1, ... , x]in the sequence, i.e., the prefix sum up to positionx.
The time complexity for both operations is O(log n).
class BinaryIndexedTree:
__slots__ = "n", "c"
def __init__(self, n: int):
self.n = n
self.c = [0] * (n + 1)
def update(self, x: int, delta: int) -> None:
while x <= self.n:
self.c[x] += delta
x += x & -x
def query(self, x: int) -> int:
s = 0
while x:
s += self.c[x]
x -= x & -x
return s
class Solution:
def getModifiedArray(self, length: int, updates: List[List[int]]) -> List[int]:
tree = BinaryIndexedTree(length)
for l, r, c in updates:
tree.update(l + 1, c)
tree.update(r + 2, -c)
return [tree.query(i + 1) for i in range(length)]class BinaryIndexedTree {
private int n;
private int[] c;
public BinaryIndexedTree(int n) {
this.n = n;
this.c = new int[n + 1];
}
public void update(int x, int delta) {
for (; x <= n; x += x & -x) {
c[x] += delta;
}
}
public int query(int x) {
int s = 0;
for (; x > 0; x -= x & -x) {
s += c[x];
}
return s;
}
}
class Solution {
public int[] getModifiedArray(int length, int[][] updates) {
var tree = new BinaryIndexedTree(length);
for (var e : updates) {
int l = e[0], r = e[1], c = e[2];
tree.update(l + 1, c);
tree.update(r + 2, -c);
}
int[] ans = new int[length];
for (int i = 0; i < length; ++i) {
ans[i] = tree.query(i + 1);
}
return ans;
}
}class BinaryIndexedTree {
private:
int n;
vector<int> c;
public:
BinaryIndexedTree(int n)
: n(n)
, c(n + 1) {}
void update(int x, int delta) {
for (; x <= n; x += x & -x) {
c[x] += delta;
}
}
int query(int x) {
int s = 0;
for (; x > 0; x -= x & -x) {
s += c[x];
}
return s;
}
};
class Solution {
public:
vector<int> getModifiedArray(int length, vector<vector<int>>& updates) {
BinaryIndexedTree* tree = new BinaryIndexedTree(length);
for (const auto& e : updates) {
int l = e[0], r = e[1], c = e[2];
tree->update(l + 1, c);
tree->update(r + 2, -c);
}
vector<int> ans;
for (int i = 0; i < length; ++i) {
ans.push_back(tree->query(i + 1));
}
return ans;
}
};/**
* @param {number} length
* @param {number[][]} updates
* @return {number[]}
*/
var getModifiedArray = function (length, updates) {
class BinaryIndexedTree {
constructor(n) {
this.n = n;
this.c = Array(n + 1).fill(0);
}
update(x, delta) {
while (x <= this.n) {
this.c[x] += delta;
x += x & -x;
}
}
query(x) {
let s = 0;
while (x > 0) {
s += this.c[x];
x -= x & -x;
}
return s;
}
}
const bit = new BinaryIndexedTree(length);
for (const [l, r, c] of updates) {
bit.update(l + 1, c);
bit.update(r + 2, -c);
}
return Array.from({ length }, (_, i) => bit.query(i + 1));
};class BinaryIndexedTree {
private n: number;
private c: number[];
constructor(n: number) {
this.n = n;
this.c = Array(n + 1).fill(0);
}
update(x: number, delta: number): void {
for (; x <= this.n; x += x & -x) {
this.c[x] += delta;
}
}
query(x: number): number {
let s = 0;
for (; x > 0; x -= x & -x) {
s += this.c[x];
}
return s;
}
}
function getModifiedArray(length: number, updates: number[][]): number[] {
const bit = new BinaryIndexedTree(length);
for (const [l, r, c] of updates) {
bit.update(l + 1, c);
bit.update(r + 2, -c);
}
return Array.from({ length }, (_, i) => bit.query(i + 1));
}type BinaryIndexedTree struct {
n int
c []int
}
func NewBinaryIndexedTree(n int) *BinaryIndexedTree {
return &BinaryIndexedTree{n: n, c: make([]int, n+1)}
}
func (bit *BinaryIndexedTree) update(x, delta int) {
for ; x <= bit.n; x += x & -x {
bit.c[x] += delta
}
}
func (bit *BinaryIndexedTree) query(x int) int {
s := 0
for ; x > 0; x -= x & -x {
s += bit.c[x]
}
return s
}
func getModifiedArray(length int, updates [][]int) (ans []int) {
bit := NewBinaryIndexedTree(length)
for _, e := range updates {
l, r, c := e[0], e[1], e[2]
bit.update(l+1, c)
bit.update(r+2, -c)
}
for i := 1; i <= length; i++ {
ans = append(ans, bit.query(i))
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Difference Array | – |
| Binary Indexed Tree + Difference Array | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Range Addition easy or hard?
Range Addition is typically classified as a medium difficulty problem. The brute force idea is straightforward, but recognizing the difference array optimization requires familiarity with prefix sum techniques.
Range Addition Python/Java solution
Most implementations build a difference array, apply boundary updates, then compute the prefix sum. The same logic works across Python, Java, C++, Go, and JavaScript. The algorithm remains O(n + k) regardless of language.
How to solve Range Addition in O(n)?
Use a difference array to mark range boundaries. For each update [start, end, inc], add inc at start and subtract inc at end + 1. After processing all updates, compute a prefix sum across the array to accumulate values. This converts k range operations into O(k) work plus one O(n) scan.
What is the best approach for Range Addition?
The optimal approach uses a Difference Array combined with a prefix sum pass. Each update marks only two positions in the array instead of modifying every element in the range. After processing all updates, a single prefix sum reconstructs the final values. This reduces the complexity to O(n + k) time and O(n) space.
Is Range Addition asked at Google/Amazon/Meta?
Range update problems using prefix sums and difference arrays appear in interviews at companies like Google, Amazon, and Meta. The exact problem may vary, but the underlying technique is commonly tested in array and prefix sum interview questions.
What data structure is used in Range Addition?
The main structure is a difference array combined with prefix sums. In advanced variants, a Binary Indexed Tree (Fenwick Tree) can also be used to support dynamic updates and prefix queries in O(log n) time.
What is the time complexity of Range Addition?
The optimal solution runs in O(n + k) time where n is the array length and k is the number of updates. Each update is processed in O(1) using the difference array, followed by a single O(n) prefix sum pass to build the final array.