370. Range Addition
Problem Description
In this problem, we are given an integer length
which refers to the length of an array initially filled with zeros. We are also given an array of update operations called updates
. Each update operation is described as a tuple or list with three integers: [startIdx, endIdx, inc]
. For each update operation, we are supposed to add the value inc
to each element of the array starting at index startIdx
up to and including the index endIdx
.
The goal is to apply all the update operations to the array and then return the modified array.
For instance, if length = 5
and an update action specifies [1, 3, 2]
, then after this update, the array will have 2
added to its 1st, 2nd, and 3rd positions (keeping zero-based indexing in mind), resulting in the array [0, 2, 2, 2, 0]
after this single operation.
After applying all updates, we need to return the final state of the array.
Intuition
The intuitive brute force approach would be to go through each update and add inc
to all elements ranging from startIdx
to endIdx
for every update in updates
. However, this would be time-consuming, especially for a large number of updates or a large range within the updates.
This is where the prefix sum technique comes into play. It is a very efficient way for handling operations that involve adding some value to a range of elements in an array. The main intuition behind prefix sums is that we can record changes at the borders ā at the start index, we begin to add the increment, and just after the end index, we cancel it out.
In more detail, for each update [startIdx, endIdx, inc]
, we add inc
to the position startIdx
and subtract inc
from endIdx + 1
. This marks the range where the increment is valid. When we compute the prefix sum of this array, it will apply the inc
increment to all elements since startIdx
, and the subtraction at endIdx + 1
will counterbalance it, returning the array to its original state beyond endIdx
.
The accumulation step goes through the array and adds each element to the sum of all previous elements, effectively applying the increments and decrements outlined in the updates.
In the presented solution, the Python accumulate
function from the itertools
module takes care of the accumulation step for us, summing up the differences and giving us the array after all updates have been applied.
Learn more about Prefix Sum patterns.
Solution Approach
The implementation of this solution is straightforward once we understand the intuition behind using prefix sums. Hereās a step-by-step rundown of the algorithm:
-
We initialize an array
d
with a length oflength
filled with zeros. This array will serve as our difference array which records the difference of each position compared to the previous one. -
We then iterate over each update in the
updates
array. Each update is in the format[startIdx, endIdx, inc]
. -
For each update, we add
inc
tod[startIdx]
. This signifies that fromstartIdx
onwards, we have an increment ofinc
to be applied. -
We then check if
endIdx + 1 < length
, which is to ensure we do not go out of bounds of the array. If we are still within bounds, we subtractinc
fromd[endIdx + 1]
. This effectively cancels out the previous increment beyond theendIdx
. -
After processing all updates,
d
now contains all the changes that are needed to be applied in the form of a difference array. -
Finally, we use the
accumulate
function of Python to calculate the prefix sum array from the difference arrayd
. This step goes through the array adding each element to the sum of all the previous elements and thus applies the increments tracked ind
at their respective starting indices and cancels them after their respective ending indices. -
The returned value from the
accumulate
function gives us the modified arrayarr
after all updates have been applied, and this is returned as the final result.
This approach effectively reduces the time complexity of the problem, as we only need to make a constant-time update for each range increment, rather than incrementing all elements within the range for each update which could lead to a much higher time complexity.
Here's the mentioned code for the described solution approach that uses these steps:
from itertools import accumulate
class Solution:
def getModifiedArray(self, length: int, updates: List[List[int]]) -> List[int]:
d = [0] * length
for l, r, c in updates:
d[l] += c
if r + 1 < length:
d[r + 1] -= c
return list(accumulate(d))
In this code example, accumulate
is an in-built Python function from the itertools
module that computes the cumulative sum of the elements. This effectively does the last step of our prefix sum implementation for us.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach with a small example.
Consider an array of length = 5
which is initially [0, 0, 0, 0, 0]
. Suppose we have the following updates = [[1, 3, 2], [2, 4, 3]]
which includes two update operations.
-
Initialize the difference array
d
which is the same size as our initial array:d = [0, 0, 0, 0, 0]
-
Apply the first update
[1, 3, 2]
:- Add the increment
2
tod[startIdx]
which isd[1]
, so nowd = [0, 2, 0, 0, 0]
. - Subtract the increment
2
fromd[endIdx + 1]
which isd[4]
, butd[4]
is out of bounds for the first update's end index, sod
remains unchanged here.
- Add the increment
-
Apply the second update
[2, 4, 3]
:- Add the increment
3
tod[startIdx]
which isd[2]
, nowd = [0, 2, 3, 0, 0]
. - Subtract the increment
3
fromd[endIdx + 1]
which is not applicable here asendIdx + 1
equals5
which is out of bounds, hence no subtraction is done.
- Add the increment
-
With all updates applied, the difference array
d
is:d = [0, 2, 3, 0, 0]
-
Now use the
accumulate
function to calculate the prefix sum array from the difference arrayd
:Final array = list(accumulate(d)) = [0, 2, 5, 5, 5]
The final array after applying all updates will be [0, 2, 5, 5, 5]
.
This example confirms that the prefix sum technique updates the initial zero-filled array efficiently with the given range update operations.
Solution Implementation
1from itertools import accumulate # Import the accumulate function from itertools
2
3class Solution:
4 def getModifiedArray(self, length: int, updates: List[List[int]]) -> List[int]:
5 # Initialize the result array with zeros of given length
6 result = [0] * length
7
8 # Iterate through each update operation described by [start, end, increment]
9 for start, end, increment in updates:
10 # Apply the increment to the start index
11 result[start] += increment
12
13 # If the end index + 1 is within bounds, apply the negative increment
14 # This is done to cancel the previous addition beyond the end index
15 if end + 1 < length:
16 result[end + 1] -= increment
17
18 # Use accumulate to compute the running total, which applies the updates
19 return list(accumulate(result))
20
21# Example usage:
22# sol = Solution()
23# print(sol.getModifiedArray(5, [[1,3,2],[2,4,3],[0,2,-2]]))
24
1class Solution {
2 // Method to compute the modified array after a sequence of updates
3 public int[] getModifiedArray(int length, int[][] updates) {
4 // Create an array 'difference' initialized to zero, with the given length
5 int[] difference = new int[length];
6
7 // Apply each update in the updates array
8 for (int[] update : updates) {
9 int startIndex = update[0]; // Start index for the update
10 int endIndex = update[1]; // End index for the update
11 int increment = update[2]; // Value to add to the subarray
12
13 // Apply increment to the start index
14 difference[startIndex] += increment;
15
16 // If the end index is not the last element,
17 // apply the negation of increment to the element after the end index
18 if (endIndex + 1 < length) {
19 difference[endIndex + 1] -= increment;
20 }
21 }
22
23 // Convert the 'difference' array into the actual array 'result'
24 // where each element is the cumulative sum from start to that index
25 for (int i = 1; i < length; i++) {
26 difference[i] += difference[i - 1];
27 }
28
29 // Return the resultant modified array
30 return difference;
31 }
32}
33
1#include <vector>
2
3class Solution {
4public:
5 // Function to calculate the modified array based on intervals of updates
6 std::vector<int> getModifiedArray(int length, std::vector<std::vector<int>>& updates) {
7 // Initialize the difference array with zeros
8 std::vector<int> diff_array(length, 0);
9
10 // Iterate through each update operation represented by a triplet [startIdx, endIdx, inc]
11 for (auto& update : updates) {
12 int start_idx = update[0]; // Starting index for the update
13 int end_idx = update[1]; // Ending index for the update
14 int increment = update[2]; // Increment value to be added
15
16 // Apply the increment to the start index in the difference array
17 diff_array[start_idx] += increment;
18
19 // Apply the negative increment to the position after the end index if in bounds
20 // This marks the end of the increment segment
21 if (end_idx + 1 < length) {
22 diff_array[end_idx + 1] -= increment;
23 }
24 }
25
26 // Iterate through the difference array to compute the final values
27 // by adding the current value to the cumulative sum
28 for (int i = 1; i < length; ++i) {
29 diff_array[i] += diff_array[i - 1];
30 }
31
32 // Return the result - the final array after all updates have been applied
33 return diff_array;
34 }
35};
36
1// Define TypeScript Function with specified input types and return type.
2/**
3 * Get the modified array after applying a series of updates.
4 * @param {number} arrayLength - The length of the array to be modified.
5 * @param {number[][]} updates - Array containing the updates to be applied.
6 * @returns {number[]} - The modified array after all updates.
7 */
8function getModifiedArray(arrayLength: number, updates: number[][]): number[] {
9 // Create an array filled with zeros of the specified length.
10 const differenceArray = new Array<number>(arrayLength).fill(0);
11
12 // Iterate over each update operation provided.
13 for (const [startIdx, endIdx, increment] of updates) {
14 // Apply the increment to the start index of the difference array.
15 differenceArray[startIdx] += increment;
16
17 // If the end index + 1 is within the bounds of the array, decrement the value.
18 if (endIdx + 1 < arrayLength) {
19 differenceArray[endIdx + 1] -= increment;
20 }
21 }
22
23 // Iterate over the array, adding the previous element's value to each current element,
24 // effectively applying the range updates.
25 for (let i = 1; i < arrayLength; ++i) {
26 differenceArray[i] += differenceArray[i - 1];
27 }
28
29 // Return the modified array with all updates applied.
30 return differenceArray;
31}
32
Time and Space Complexity
The given Python code utilizes the prefix sum (accumulation) strategy to compute the results of multiple range updates on an array. The analysis of the time and space complexity is as follows:
-
Time Complexity:
- The algorithm iterates over the
updates
list once. If there arek
updates given, this part of the algorithm has a time complexity ofO(k)
. - Each update operation itself is constant time (i.e.,
O(1)
), since it only involves updating two elements in thed
array: the start index and the end index (or one past the end index). - After applying all updates, the algorithm uses
accumulate
from theitertools
module to compute the prefix sums over the entired
array. Computing the prefix sum of an array of lengthn
is anO(n)
operation.
Combining the two parts, the overall time complexity of the algorithm is
O(k + n)
. - The algorithm iterates over the
-
Space Complexity:
- The space complexity of the algorithm is primarily determined by the
d
array, which holds the prefix sum and has a length equal to the inputlength
. Therefore, it isO(n)
, wheren
is the length of the result array. - The
updates
list does not count towards the extra space since it is part of the input. - All other operations use constant space, meaning they do not depend on the size of the input, hence do not significantly contribute to the space complexity.
Therefore, the space complexity is
O(n)
. - The space complexity of the algorithm is primarily determined by the
In conclusion, the given algorithm has a time complexity of O(k + n)
and a space complexity of O(n)
.
Learn more about how to find time and space complexity quickly using problem constraints.
Which algorithm should you use to find a node that is close to the root of the tree?
Recommended Readings
Prefix Sum The prefix sum is an incredibly powerful and straightforward technique Its primary goal is to allow for constant time range sum queries on an array What is Prefix Sum The prefix sum of an array at index i is the sum of all numbers from index 0 to i By
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!