This is the leetcode problem from a recent contest: https://leetcode.com/problems/minimum-number-of-seconds-to-make-mountain-height-zero/
For some reason, this solution gives a TLE: https://ideone.com/00tSfJ.
I have an alternative solution which passes, my question is why does the above solution give TLE?
This solution should not be giving TLE because:
-the while loop can have upto 56 turns (since 2^56 > 1e8 * 1e8)
-the for loop upto 10^4 turns
-and, the map.upper_bound() would take 17 turns (since, log_base2(2^17) > log_base2(10^5) > log_base2(no. of items in map))
So overall, 9.52 * 10^6 operations. But I still get a TLE here. Please help me understand this better.
PS: I know that above is a simplification because complexity represents order of growth with respect to input size but I still don't see why the above solution should not pass.
Why would you use a map to store it? you can use binary search to find it in log, while with lower constant factor, or you can find it in O(1) with some math.
I did find it in O(1), my question is why this solution fails when it still falls within the limits of total calcs allowed on Leetcode.
I think one of the following happened:
a) There's a part of your code that causes undefined behavior, causing the program to crash (giving TLE)
b) The constant factor of the map is simply too large