• + 0 comments

    My Javascript solution:

    function arrayManipulation(n, queries) {
        // creating an array with the values needed to form the result array
        let sumArray = Array(n + 1).fill(0)
        queries.forEach(q => {
            let a = q[0] - 1
            let b = q[1]
            let k = q[2]
            
            sumArray[a] += k
            sumArray[b] -= k
        })
        
        // actually creating the result array
        let currentValue = 0
        sumArray.forEach((s, i) => {
            currentValue += s
            sumArray[i] = currentValue
        })
        
        // extracting the maximum value
        let maxValue = 0
        sumArray.forEach(s => {
            if(s > maxValue) {
                maxValue = s
            }
        })
        
        return maxValue
    }
    

    The key point to understand from this solution is that the goal is to reduce the big O, and the way we do this is by avoiding the most logical way to approach this problem, which could be a nested loop. For example, we could loop through the queries array and then, inside it, loop n times to perform each operation in order to form the final array. But this would result in O(mn) time complexity.

    Now, it's worth noticing that it doesn't really matter how many loops we go through, as long as they're not nested.

    That's why in my solution, I don't iterate the queries array in order to form the final array, but instead, I go through it to form an array that allows me to form the final array by iterating it afterwards.

    Let me give you an example. Let's say that I get this input: n **= 5 **a b k 2 4 2

    Then, my resulting array after iterating the queries array would be: [0, 2, 0, 0, -2, 0] (remember that my array size is n+1 to store the last substraction, but is not relevant)

    That doesn't tell us much at first glance, but if we iterate that array assigning the value of the summatory to each position, the result array would be: [0, 2, 2, 2, 0, 0]

    Here's how: 0 0 + 2 = 2 2 + 0 = 2 2 + 0 = 2 2 + (-2) = 0 0 + 0 = 0 // this last element is just for calculation purposes

    And... That's how we got the resultant array without nested loops!

    Once I have the resultant array I just need to find the Max value of it.

    As you can see I used 3 loops which results in O(a + b + c) but as you know, we dont care about less dominant terms so that can be reduced to O(n).

    Hope this explanation helps to understand the solution.