CODEWITHSUNDEEP
javaloopstime-complexity
Pixie
Pixie

Reputation: 311

What's the best way to improve time complexity with multiple FOR loops

I am trying to solve THIS Hackerrank problem in Java and I output the correct value, however I don't pass all the tests due to timeout (when with huge input) since I ended up having 7 "FOR" LOOPS.. can you advise since I am kind of new with programming, what's the best way to reduce these for loops. Loops do the following:

Loop 1: Splits the input at every space and assigns each value to a String array
Loop 2: Converts the String to Int and assigns each int value to an Int version of the array, to allow for calculations
Loop 3: Repeat Loop 1, but this time for the Query input
Loop 4: Repeat Loop 2, but this time for the Query input
Loop 5: OUTER LOOP to go over each Q
Loop 6: Inner loop 1 of Loop 5 to go over each Array value and sum the curr value with the curr query value
Loop 7: Inner loop 2 of Loop 5 to go over the updated Array values and sum them up by first getting their absolute values

So.. after so many loops the complexity is a disaster. Any ideas how to improve it?

Upvotes: 0

Views: 477

Answers (1)

fgb
fgb

Reputation: 18559

The time-complexity is mostly down to the last nested loops. Iterating over all the queries and the whole array is 100000 * 100000 = 10000000000 iterations, which is too many. You need to iterate over both these arrays, but not in a nested way. You can only afford to do about log(100000) iterations within any query. The problem page hints at a binary search, which is logarithmic, so that should do.

The sample input is an array of [-1, 2, -3] with queries [1, -2, 3].

The array can be in any order, so you can start by sorting the array to get [-3, -1, 2].

With the first query 1, we get the array [-2, 0, 3]. There's not enough time to iterate over the array here, so instead think about how the answer is different from the initial array:

  • The 2 has changed to a 3, so the sum increases by 1. Any number that remains positive will have the same increase.

  • The -3 has changed to a -2, so the sum decreases by 1. Any number that remains negative will have the same decrease.

  • The -1 has changed to a 0, so the sum decreases by 1. This is similar to above.

  • There aren't any numbers here that change their sign, but check what happens to them as well. If the array is sorted, then they will all be adjacent values in the array. Here, it helps the know the sum of any range of values in the original array. These can be precalculated by storing the sums of each prefix of the array.

Note it may be easier if all the numbers were positive to begin with, so you could transform the problem to an array of [2, 5, 0] and queries [-3, 1, -2, 3], then don't output the first answer.

We know the sum of the original array is 6, so the new sum is 6 + 1 - 1 - 1 = 5. If we know how many numbers there are that are positive or negative (try a binary search), and how they fit into the cases above, then each sum is just a few multiplications, additions and subtractions.

Upvotes: 1

Related Questions