I was working on a problem on HackerRank called Algorithmic Crush (now titled “Array Manipulation”) and I thought the efficient solution was interesting and worth sharing.
Problem
You are given the size of a 1-indexed array and a list of operations to perform. Perform each operation on the array and return the maximum value in the array after all operations have been completed.
Let’s go through an example.
Our example array has 8 elements (represented by n) and we are going to perform 3 operations on the array (represented by m).
n = 8
m = 3
The operations are given as a list of 3 values: a, the left index, b, the right index, and k, the value to add to the array. To perform an operation, we add the value k to each array element between the two given indices, inclusive.
Here are the 3 operations and their values: a, b, and k:
a b k
1 4 5
2 5 3
4 8 1
Here is the array after each operation:
index -> 1 2 3 4 5 6 7 8 a b k
[0, 0, 0, 0, 0, 0, 0, 0]
[5, 5, 5, 5, 0, 0, 0, 0] 1 4 5 "Add 5 to indices 1 to 4"
[5, 8, 8, 8, 3, 0, 0, 0] 2 5 3 "Add 3 to indices 2 to 5"
[5, 8, 8, 9, 4, 1, 1, 1] 4 8 1 "Add 1 to indices 4 to 8"
The maximum value in the final array is 9 at index 4.
Here are the problem constraints:
3 <= n <= 10^7
1 <= m <= 2 * 10^5
1 <= a <= b <= n
0 <= k <= 10^9
Simple Solution
The simple solution to this problem is to create an array of size n and perform the operations exactly as they are described in the problem statement.
Let’s write that out in code.
We create an array of size n and add the value k to each array element between the given indices, inclusive. While we’re adding k to the array, we keep track of the largest value we’ve seen with a variable, max, and update it whenever we see a larger value.
Here is the simple solution in Java:
long[] arr = new long[n];
long max = 0;
for (List<Integer> operation : operations) {
int a = operation.get(0);
int b = operation.get(1);
long k = operation.get(2);
for (int i = a; i < b + 1; i++) {
arr[i - 1] = arr[i - 1] + k;
max = Math.max(max, arr[i - 1]);
}
}
return max;
This solution works, but its runtime is O(n × m) because in the worst case scenario we’re updating n elements of the array m times.
The space complexity is O(n) because we’re storing an an array of n elements.
How can we improve this?
My Thought Process
(If you want to skip to the efficient solution, follow this)
I began to think of a more efficient solution to this problem. What is the bare minimum amount of data we need to store? Can we get away with storing less than n elements?
I thought of a solution where instead of using an array of size n, I would create a hashmap that maps each index we update to its value. That would save space in the case where n is large and m (the number of operations) is small. It would require more space than a simple array when m is as large than n though. Similarly, the runtime would be better than the simple array solution if the final array is sparse, and worse when the final array is dense. After thinking it over, I don’t think that solution would be more efficient for most scenarios.
For the worst case scenario when the final array is dense, I don’t think our space complexity can be better than O(n).
How can we reduce the runtime?
I thought about how updating every element between a and b could be made more efficient. What if we stored k and the difference between a and b at index a in a list?
For example, if the array has 3 elements and the first operation is:
a b k
1 3 5
We would create a list of n tuples, with each tuple storing k and the difference between a and b. For example:
[ [5, 2], [0, 0], [0, 0] ]
With k = 5 and b - a = 2. Then to calculate the max value we would iterate over every element in the list. The first element would tell us this index’s value is 5 and we need to add 5 to the next two elements.
Wait, that wouldn’t work. What if the next operation was:
a b k
1 2 7
We can’t store two different values of k with different ranges at the first index. What if we created a two dimensional dynamic list like this?
[ [5, 2], [0, 0], [0, 0] ]
|
V
[7, 1]
That begins to make things complicated. I would have to make multiple stacks and pop elements in the right order to take into account overlapping operation ranges. I don’t think this would more efficient than the simple solution.
Efficient Solution
Thanks to the HackerRank discussion section, I saw a creative way to solve this problem and adapted it so it’s easy to understand.
In the efficient solution, instead of updating every array element between the array indices (as we did in the simple solution), we just update the array elements at the beginning and end of the given ranges.
Let’s look at an example where n = 3 and the first operation is:
a b k
1 3 5
We create an array of size n + 1 (in this example, 4 elements). Then we add k to index a and subtract k from index b + 1. Here is what the array would look like after the first operation:
index -> 1 2 3 4 a b k
[0, 0, 0, 0]
[5, 0, 0,-5] 1 3 5
To find the max value, we first keep track of a new variable called sum. We iterate over the array and add the value at the current index to sum. At every index we check if sum is larger than the current max value. When we reach the end of the array, we will have the maximum value.
Let’s find the max value of the example. I labeled the sum and max values at every index:
index -> 1 2 3 4
[5, 0, 0,-5]
sum -> 5 5 5 0
max -> 5 5 5 5
Starting at the first index, we add 5 to the sum, then add 0, add 0, and add -5 at the last index. The maximum value sum reached was 5, and that’s the answer.
What happens when the second operation is:
a b k
1 2 7
We add 7 to index a (1), subtract 7 from index b + 1 (3), and go through the same process to calculate the max value. Here is the array:
[12, 0, -7, -5]
Here are sum and max at every index:
[12, 0, -7, -5]
sum -> 12 12 5 0
max -> 12 12 12 12
When we reach the end of the array, max is 12 and that is the answer.
Here is the efficient solution written in Java:
long[] arr = new long[n + 1];
for (int i = 0; i < operations.size(); i++) {
List<Integer> operation = operations.get(i);
int a = operation.get(0);
int b = operation.get(1);
int k = operation.get(2);
arr[a - 1] += k;
arr[b] -= k;
}
long sum = 0;
long max = 0;
for (int i = 0; i < n; i++) {
sum += arr[i];
max = Math.max(max, sum);
}
return max;
What is the runtime and space complexity of the efficient solution?
The runtime of the algorithm is O(n + m) because we have to initially add 2m values to the array and then iterate over n elements to calculate the max value.
The space complexity is the same as the simple solution, O(n), because we’re storing an array of size n + 1 in memory.
Final Notes
You can find this solution and other HackerRank problem solutions in my GitHub repository here.