Reg: Time limit exceeded.


  • 3
    P

    Hi all,
    I've written the code in suchaway that my solution validates all possible starting positions. I know that this is a very inefficient code to find the solution and finally i got time limit exceeded. can anybody give suggestions on how to solve this in an efficient way. I don't need code but logic fine.

    Thanks
    pavan kumar


  • 5
    S

    Here is an answer by denny5 from old discuss. Thanks to denny5!

    At each station, given the gas and cost, the net gas left when arriving next station is gas[i] - cost[i].

    Each station has a net gas < 0 will not be a start station. For each station, if there is an accumulation net gas < 0, this station can't be a start station. Also, if the accumulation gas from station i to j is negative, all these stations can't be start station. (assumed that we checked it was still position before station j. If we started from any station from i to j, it will become negative after j). So we can safely loop only one pass.

    As you wish, I won't share denny5's code for you. But I think the statement is enough for you to come up a efficient solution.


  • 0
    P

    Hi Shangrila,
    Thanks for your explanation. coming to the coding part, I'll give it a try. :)


  • 7
    X

    Leetcode's facebook page has post an announcement of TLE on java implementation, it seems they are more restricted to brute force algorithms.

    For this problem, a linear algorithm exists. So try to be O(n). In fact, theta n.

    My linear solution based on a observation that, if you stops at certain gas station, the gas stations previous to the station you stop must not be a valid starting point. So all you need is just circle once, if you don't have enough gas, then start from next stop. In worst case, you will go through 2N gas stations. and In best case, you will go through N gas stations. So the time complexity is theta N. and Space complexity is constant.

    So, simply start from the first station, and if you come back, return that station. If you stop at certain station, start from the next station. When you circle once from some station, return that station, when you starting point is greater than gas.length, it means no station can be a starting point, so return -1.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.