Skip to main content
Talentd

Range Addition - Solution & Explanation

MediumPremiumFree on FleetCodeArrayPrefix Sum12 min readAsked at: Amazon, Google
Practice this problem

Problem Statement

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 <= 105
  • 0 <= updates.length <= 104
  • 0 <= 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.

Code

PythonJavaC++GoTypeScriptJavaScript

Python

Java

C++

Go

TypeScript

JavaScript

Try this approach in the editor →

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:

  1. Point Update update(x, delta): Add a value delta to the number at position x in the sequence.
  2. Prefix Sum Query 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).

Code

PythonJavaC++GoTypeScriptJavaScript

Python

Java

C++

Go

TypeScript

JavaScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Difference Array—
Binary Indexed Tree + Difference Array—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Range UpdatesO(n * k)O(1)Small arrays or very few updates where simplicity matters more than performance
Difference Array + Prefix SumO(n + k)O(n)Best general solution when applying many range updates offline
Binary Indexed Tree + Difference ArrayO((n + k) log n)O(n)Useful when updates and prefix queries must be handled dynamically

Video Solution

Range Addition | Arrays & Strings • Pepcoding • 19,652 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Range Addition with our built-in code editor and test cases.

Practice on FleetCode
Previous

Count Positions on Street With Required Brightness

Next

Range Addition II