Range Addition Problem in Java
In this article, we will discuss the Range Addition Problem in Java. In the Range Addition problem, elements in an array are updated within given ranges. Given an array of length N and a list of updates in the format [startIndex, endIndex, increment], the challenge is efficiently computing the final changed array after applying all updates.
Notably, the increment value is added to startIndex and subtracted from endIndex + 1 in the result array.
Increment at startIndex:
result[startIndex] += increment
Subtract at endIndex + 1:
result[endIndex + 1] -= increment
Example 1:
Input: int length = 4
int[][] updates = {{0, 1, 2}, {1, 2, 3}}
Output: [2, 5, 3, 0]
Explanation: The initial update, [0, 1, 2], increments the element at startIndex 0, yielding the array [2, 0, 0, 0]. The subtraction at endIndex + 1 (2) changes the array to [2, 0, -2, 0]. The second update, [1, 2, 3], increments the element at startIndex 1, resulting in [2, 3, -2, 0]. The subtraction of endIndex + 1 (3) yields [2, 3, -2, -3]. Following the cumulative sum, we obtain:
result[0] = 0+2
result[1] = 2+3
result[2] = 5-2
result[3] = 3-3
The final output is [2, 5, 3, 0].
Implementation: Iterative
Let's look at how to do the above-mentioned range addition.
FileName: RangeAddition.java
public class RangeAddition {
public static void main(String[] args) {
int length = 4;
int[][] updates = {{0, 1, 2}, {1, 2, 3}}; // Updates in the form [startIndex, endIndex, increment]
int[] result = getModifiedArray(length, updates);
// Print the modified array
for (int i = 0; i < result.length; i++) {
System.out.print(result[i] + " ");
}
}
public static int[] getModifiedArray(int length, int[][] updates) {
int[] result = new int[length];
for (int i = 0; i < updates.length; i++) {
int startIndex = updates[i][0];
int endIndex = updates[i][1];
int increment = updates[i][2];
// Update the start index of the range
result[startIndex] += increment;
// If endIndex+1 is within the array bounds, subtract the increment from endIndex+1
if (endIndex + 1 < length) {
result[endIndex + 1] -= increment;
}
}
// Perform cumulative sum to get the final modified array
for (int i = 1; i < length; i++) {
result[i] += result[i - 1];
}
return result;
}
}
Output:
2 5 3 0
Complexity Analysis:
The program's overall time complexity is O(N), where N is the maximum number of updates and array length. The additional array required to store intermediate results increases the space complexity to O(N). This program is efficient, especially when the number of updates is much less than the array length.
Implementation: Dynamic Programming
Here, we create a DP array to track the cumulative sum directly rather than performing it in a separate loop.
FileName: RangeAddition1.java
public class RangeAddition1 {
public static void main(String[] args) {
int length = 4;
int[][] updates = {{0, 1, 2}, {1, 2, 3}}; // Updates in the form [startIndex, endIndex, increment]
int[] result = getModifiedArray(length, updates);
// Print the modified array
for (int i = 0; i < result.length; i++) {
System.out.print(result[i] + " ");
}
}
public static int[] getModifiedArray(int length, int[][] updates) {
int[] result = new int[length];
for (int i = 0; i < updates.length; i++) {
int startIndex = updates[i][0];
int endIndex = updates[i][1];
int increment = updates[i][2];
// Update the start index of the range
result[startIndex] += increment;
// If endIndex+1 is within the array bounds, subtract the increment from endIndex+1
if (endIndex + 1 < length) {
result[endIndex + 1] -= increment;
}
}
// Perform cumulative sum directly in the same loop
int prefixSum = 0;
for (int i = 0; i < length; i++) {
prefixSum += result[i];
result[i] = prefixSum;
}
return result;
}
}
Output:
2 5 3 0
Complexity Analysis:
The time complexity is O(N), where N is the maximum of the number of updates and the length of the array, as a result of iterating through updates and adding them together. The space complexity is also O(N), which is due to the additional array needed to store intermediate and final findings. The program makes the best use of the prefix sum strategy for efficient array change.