Range Addition | Arrays & Strings
Range Addition - Video Solution
Watch 10 video solutions for Range Addition, a medium level problem involving Array, Prefix Sum. This walkthrough by Pepcoding has 19,652 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 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.
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 |