HackerRank – Array Manipulation Solution in JavaScript – O(n) Time

Array Manipulation is a coding challenge with hard difficulty in the HackerRank data structures category. In this blog post, we’ll discuss how we can solve it in JavaScript in O(n) time and O(n) space complexity.

Problem Statement

Starting with a 1-indexed array of zeros and a list of operations, for each operation add a value to each the array element between two given indices, inclusive. Once all operations have been performed, return the maximum value in the array.

Read full details and access the challenge on Array Manipulation | HackerRank

Note

The initial question in itself is actually pretty simple, you just have to follow the instructions and you’ll get the correct results. But it is in the hard category for a reason, right?

If you do it intuitively like me, looping through each query and adding each elements resulting in a nested loop, you’ll be having performance issues and getting time limit exceeded in the test cases.

So, I have 2 solutions below, the incorrect and the optimized version. Incorrect version still gives the right answers but it just has performance issues. Feel free to skip to the optimized solution if you’ve understood the intuitive solution.

Intuitive Solution (Incorrect)

function arrayManipulation(n, queries) {
    let arr = [];
    for (let i = 0; i < n; i++) {
        arr.push(0);
    }
    queries.forEach(query => {
        for (let i = query[0]; i <= query[1]; i++) {
            arr[i-1] += query[2];
        }
    })
    return Math.max(...arr);
}

Time Complexity : O(n*m)

Space Complexity : O(n)

This is an intuitive solution and I bet most of you have came up with this solution too.

We just create an array, fill the array according to the instructions (add value k from index a to b). If you notice, we use arr[i-1] instead of arr[i], that’s because a and b is meant for 1-indexed array, but we used o-indexed array so we have to subtract it by 1.

Then, we return the max value.

Since we have a nested loop from 2 different arrays, we have O(n*m) complexity and we have O(n) space because we used an array too.

O(n*m) is not fast enough and that’s the real challenge, so we’ll optimize it.

Optimized Solution (Solved)

function arrayManipulation(n, queries) {
    let arr = new Array(n).fill(0);
    queries.forEach(query => {
        let [a, b, k] = query;
        arr[a-1] += k;
        arr[b] -= k;
    })
    let [max, sum] = [0, 0];
    arr.forEach(val => {
        sum += val;
        max = sum > max ? sum : max;
    })
    return max;
}

Time Complexity : O(n)

Space Complexity : O(n)

This solution is optimized for the purpose of finding the max number.

Instead of filling the array by adding from index a to b, we only add k to index a and subtract k from b+1 (Remember, a and b is for 1-indexed array, but we used 0-indexed so there’s the +1). We do this to balance the summing process later on.

Then we loop through the array and summing up all the values and keep the highest value at any point as the max value.

Finally, we return max.

Now we don’t have a nested loop anymore and only have 2 separate loops, so we have O(n+m) time to be precise or in more generic term, O(n) time complexity.

Since we also used an array, we have O(n) space complexity.

Example Walkthrough

To make it clearer, let’s walk through an example for the optimized solution.

5 3
1 2 100
2 5 100
3 4 100

We have an array with n or in this case 5 0-values, [0, 0, 0, 0, 0] and 3 queries that means we iterate 3 times.

There are 2 loops in our code, the array value change in the first loop goes like this for each iteration :

1. [100, 0, -100, 0, 0]
2. [100, 100, -100, 0, 0, null]
3. [100, 100, 0, 0, -100, null]

Now, it’s easier to understand, right? You can see that if we sum up the array we can find the max value. So, that’s what we’ll do in the second loop.

Since our array now have 6 elements, the loop goes like this :

You can see that the numbers added nicely and we got our max value.

Conclusion

That’s how you can solve the Array Manipulation Challenge in HackerRank.

This is a really good practice. It teaches you how to first think of a correct solution and then optimize it down from O(n*m) to just O(n).

Let me know in the comments if you find this blog helpful or if you have further questions! Feedbacks would be appreciated!

Check out the rest of my blog for more helpful contents on Data Structures and Algorithms in JavaScript! We’ll also discuss more HackerRank solutions using JavaScript in this blog!

See you next post!