Algorithm Optimization

Hackerrank Array Manipulation

So I tried to solve this problem and my solution kept timing out on the tests with huge inputs. I believe one such input was where your array of zeros' count was 100,000 and at least 10,000 lines of math additions you had to do to it.

func maxArrayQueries(n: Int, queries: [[Int]]) -> Int {
    var zeros = Array(repeating: 0, count: n)

    for i in 0..<queries.count {
        let startIndex = (queries[i][0]-1)
        let endIndex = (queries[i][1]-1)
        
        for j in startIndex...endIndex {
            zeros[j] += queries[i][2]
        }
    }
    guard let max = zeros.max() else { return 0 }
    return max
}

This is my solution and I couldn't think of a way to optimize it further. After hitting this roadblock i researched some and think maybe the additions caused the ints within the array to become too big? So its hitting a BigInt problem in swift? That's my only guess as to what was happening. If anyone could give this a look over I would greatly appreciate it! Thank you in advance for your time.

You never change the size of the array right? Only changing the value stored in there.

I'm not sure I understand what you mean by this. In any case, if an operation results in value too large/small to be stored, Swift will just crash. So "timeout" would not be what you observe.


As a hint, say n == 1000, what'd happen if a and b never fall in the range [2, 999] in any of the query? What unnecessary work would the code be doing? How common could that be if n == 1e+7 and m == 2e+5?

Can you provide an example of the problematic input?

1000 100
1 1000 1
1 1000 1
1 1000 1
...

@GalCohen wait, are you asking me, or the op?

OP, sorry guess i didn't reply correctly.

Okay so I suppose what Im not understanding in the optimal solution is this:

Blockquote

  • Doing this kind of update, the number in the array will be prefix sum of array from index 1 to i because we are adding to the value at index and subtracting from the value at index and taking prefix sum will give us the actual value for each index after operations .

Can someone explain in a different way what this means? I think I just can't visualize how this is going to arrive at the correct answer

Likely you did reply correctly. Just that this site is unable to distinguish reply to last ppl, or the thread as a whole.

Sorry Hackerrank apparently doesn't allow you to view their inputs after your test is completed. I tried to download some but the folder prevents opening without permission

This is getting into SO territory. You'd probably get better help there.

Anyway, prefix sum is a method of getting the "sum" of multiple ranges quickly.

Essentially if you have

[a0, a1, a2, a3, a4, a5, ...]

And you want to compute

s0 = a0
s1 = a0 + a1
s2 = a0 + a1 + a2
s3 = a0 + a1 + a2 + a3
...

You can quickly compute the next row, by adding the value from the previous row: s3 = s2 + a3 for example.

So if you have an array, you can do

var s = 0
for a in array {
  s += a
  // now we have `s` do what ever we want with it.
}

And what the solution is saying is that, when a new query comes in, you can change values of a in a way that array of s corresponds to the resulting array (one you want to find max value from).

1 Like

Thank you everyone for your help. It turns out I've just never encountered a prefix sum before. I had zero knowledge of such a concept so that's why it wasn't sinking in. After some YouTubing of it I now understand why the optimal solution works and of course is more efficient than my initial brute force approach :slight_smile:

Thank you!

1 Like