Array Manipulation JavaScript Solution

#hackerrank #arrays #javascript

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.

Setup

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.

Example

n = 12;
queries = [
// Start, end, value to add
    [2,   7,   4],
    [5,   9,   2],
    [6,   12,  8]
]
/*
 1   2   3   4   5   6   7   8   9   10  11  12 // Indices
*/
[0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0] // Starting array
[0,  4,  4,  4,  4,  4,  4,  0,  0,  0,  0,  0] // After queries[0]
[0,  4,  4,  4,  6,  6,  6,  2,  2,  0,  0,  0] // After queries[1]
[0,  4,  4,  4,  6,  14, 14, 10, 10, 8,  8,  8] // After queries[2]

largest = 10

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

function arrayManipulation(n, queries) {
    let arr = new Array(n + 1).fill(0);
    let max = 0;
    queries.forEach(([a, b, k]) => {
        for (let i = a; i <= b; i++) {
            arr[i] += k;
            if (arr[i] > max) {
                max = arr[i];
            }
        }
    })
    return 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.

But you know what? There's no shame in not knowing how to solve this problem. It's marked as hard and it is hard. I had to look up solutions in the Discussion section to grok how one would even approach solving this problem at scale. And then I needed to take out a piece of paper and a pen to work through a few problems to understand how the provided solution worked. This is one of those solutions that once you understand it, it seems obvious. And it's beautiful. Naturally, the solutions I found were all in either C++ or Java and that's not my language of choice for code challenges, so I adapted it into JavaScript to both ensure that I understood it and to make it easier for anyone looking to solve it in JavaScript.

Solution

SPOILERS!

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

Let's go through how this works using the earlier example. Note that the reason we're changing the value at arr[a - 1] is because the problem statement indicated that the arrays are 1-indexed, so the array indices given are going to be off by 1 since arrays in JavaScript are 0-indexed. The reason we change arr[b] and not arr[b-1] is that the operations are meant to be from a to b inclusive and so we want to add the end point as being after the last index operated on.


n = 12;
queries = [
// Start, end, value to add
    [2,   7,   4],
    [5,   9,   2],
    [6,   12,  8]
]
/*
 1   2   3   4   5   6   7   8  9  10 11  12  13 // Indices
*/
 [0, 0,  0,  0,  0,  0,  0,  0, 0,  0, 0,  0,  0] // Starting array
 [0, 4,  0,  0,  0,  0,  0, -4, 0,  0, 0,  0,  0] // After [2,7,4]
 [0, 4,  0,  0,  2,  0,  0, -4, 0, -2, 0,  0,  0] // After [5,9,2]
 [0, 4,  0,  0,  2,  8,  0, -4, 0, -2, 0,  0, -8] // After [6,12,8]

sum = 0, max = 0, arr = [0,4,0,0,2,8,0,-4,0,-2,0,0,-8]
sum += 0; // sum stays 0, max stays 0
sum += 4; // sum is now 4, sum > max, so max becomes 4
sum += 0; // sum stays same, max stays same
sum += 0; // sum stays same, max stays same
sum += 2; // sum is now 6; sum > max, so max becomes 6;
sum += 8; // sum is now 14; sum > max, so max becomes 14;
sum += 0; // sum stays same, max stays same
sum += -4; // sum is 10; max > sum, so max stays 14;
sum += 0; // sum stays same, max stays same
sum += -2; // sum is 8; max > sum, so max stays 14;
sum += 0; // sum stays same, max stays same
sum += 0; // sum stays same, max stays same
sum += -8; // sum is 0; max > sum, so stays 14;

max = 14;

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. And 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