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.

Description Hints 4 Solution Video 24:34

370. Range Addition

Medium73.0% acceptance2 companiesPremium elsewhere, free here

You are given an integer length and an array updates where updates[i] = [startIdx_i, endIdx_i, inc_i].

You have an array arr of length length with all zeros, and you have some operation to apply on arr. In the i^th operation, you should increment all the elements arr[startIdx_i], arr[startIdx_i + 1], ..., arr[endIdx_i] by inc_i.

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 <= 10⁵
0 <= updates.length <= 10⁴
0 <= startIdx_i <= endIdx_i < length
-1000 <= inc_i <= 1000

Asked at 2 companies

Google Amazon

Topics

Array Prefix Sum

Hints open one at a time

Hint 1

Thinking of using advanced data structures? You are thinking it too complicated.

Hint 2

For each update operation, do you really need to update all elements between i and j?

Hint 3

Update only the first and end element is sufficient.

Hint 4

The optimal time complexity is O(k + n) and uses O(1) extra space.

24:34

Still stuck?Read 2 approaches, or watch a walkthrough.

Open solution