Problem Statement: Starting with a 1-indexed array of zeros and a list of operations, for each operation add a value to each of the array elements between two given indices, inclusive. Once all operations have been performed, return the maximum value in the array.
The function you are writing takes two arguments. The first argument, n, represents the number of elements in the array you are performing operations on. The second argument, queries is an array of operations to perform on the array. Each element in queries is an array consisting of a starting index, ending index, and the value to be added to the elements in your array between those starting and ending indices.
Naive Approach (Brute Force)
- Create an array with length of n + 1
- Initialize each element in the array with 0
- Create a variable to store the maximum value encountered, initialized to 0
- Iterate through queries array, separating out a, b, k
- Loop through the array from index a through b, incrementing each element at that index by k
- If the updated value of the array at the current index is greater than the max, update max
Now, this works for some input. But think about what happens when n is a large number. Think about what happens if queries is a large array. In each operation in queries, you’re updating 1-n elements in the array. That’s a lot of operations to be performing. So some of the tests on HackerRank for this particular problem time out if you have a function like this as a solution. Their input is just too large to get away with using this algorithm. Womp womp. Sad trombone.
How does this work? Well, because we’re subtracting the value of k at the index following the end index, we’re only adding the value of a given k for the indices we should have added that k to. Because we’re only changing the values in the array to mark the beginning and end of operations, we’re only performing 2 updates for each query. We’ve changed a variable operation with a worst case complexity of n to be constant! Not too shabby.
Problem taken from HackerRank