📘 Problem Statement
You are given an integer length of an array, initialized with zeros. You are also given a 2D array of operations, where each operation consists of three integers: start, end, and inc. For each operation, you need to add inc to all elements of the array from index start to index end (both inclusive).
Return the modified array after all operations are applied.
🧠 Key Insight
This problem can be solved efficiently using a technique called the difference array or prefix sum trick. The idea is to update only the beginning and the end+1 of the affected range and then compute the final array by accumulating the values.
Steps:
- Use a Difference Array: Instead of updating all elements from
start to end, just mark the start of the addition and the point just after the end.
- Final Array Construction: After applying all operations in this way, simply take the cumulative sum of the array to get the final result.
💡 Approach
- Initialize the Array: Start by initializing an array
res of size length filled with zeros.
- Apply Operations Using the Difference Array Technique:
- For each operation, increment the
start index by inc and decrement the end+1 index by inc.
- Compute the Final Result:
- After processing all operations, compute the cumulative sum to apply the range additions effectively.
This approach works efficiently with a time complexity of O(n + m), where n is the size of the array and m is the number of operations.
🐍 Python Code
python
class Solution:
def getModifiedArray(self, length: int, updates: list) -> list:
# Initialize the result array with 0's
res = [0] * length
# Apply all updates to the difference array
for start, end, inc in updates:
res[start] += inc
if end + 1 < length:
res[end + 1] -= inc
# Compute the final array by accumulating the values
for i in range(1, length):
res[i] += res[i - 1]
return res
🔍 Step-by-Step Explanation
1. Initialize the Array
python
res = [0] * length
- Create an array
res of size length filled with zeros. This will represent the modified array after all operations are applied.
2. Apply Range Updates
python
for start, end, inc in updates:
res[start] += inc
if end + 1 < length:
res[end + 1] -= inc
- For each operation
(start, end, inc), increment res[start] by inc to mark the start of the range addition.
- Decrement
res[end + 1] by inc to mark the end of the range addition, which ensures that when we accumulate the values, the range update stops at end.
3. Compute the Final Result
python
for i in range(1, length):
res[i] += res[i - 1]
- Traverse the array
res and compute the cumulative sum to apply all range updates. The element at each index is updated to the sum of all previous values, which gives the correct result.
💡 Example
python
Input:
length = 5
updates = [[1, 3, 2], [2, 4, 3], [0, 2, -2]]
Output:
[-2, 0, 3, 5, 3]
Explanation:
Initially, the array is [0, 0, 0, 0, 0].
- After applying the first operation [1, 3, 2], the array becomes [0, 2, 2, 2, 0].
- After applying the second operation [2, 4, 3], the array becomes [0, 2, 5, 5, 3].
- After applying the third operation [0, 2, -2], the array becomes [-2, 0, 3, 5, 3].
⏱️ Time & Space Complexity
MetricComplexityTime ComplexityO(n + m)Space ComplexityO(n)
- Time Complexity: The algorithm runs in O(n + m) time, where
n is the size of the array and m is the number of operations. We process each operation once and accumulate the array in a second pass.
- Space Complexity: The space complexity is O(n) due to the space required for the result array
res.
🧵 Final Thoughts
The Range Addition problem demonstrates the power of difference arrays in efficiently solving range update problems. The approach reduces the need for direct element-wise updates, making the solution scalable even for large inputs.
- Difference Array Technique: Instead of updating every element in a range, we simply mark the start and end+1 of the range, making the update operation O(1) per operation.
- Cumulative Sum: After all operations are applied, we use a cumulative sum to get the final result in linear time.
This method is both time-efficient and space-efficient, making it ideal for problems involving range updates.