Range Addition - Video Solutions

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.