A simple T(n):S(1) solution


  • 0
    G

    Scan the list backwards and accumulate the cost difference. After the scan is complete, if the cumulative cost difference is >= 0, then the station with the highest cumulative cost difference is the place to start. Otherwise return -1.

    Notation: T(n) => Time complexity is O(n); S(1) => Space complexity is O(1)

    class Solution {
        public int canCompleteCircuit(int[] gas, int[] cost) {
            int n = gas.length;
            int max = gas[n-1] - cost[n-1];
            int total = max;
            int ans = n-1;
            
            for (int i = n-2; i >= 0; i--) {
                total += gas[i] - cost[i];
                if (total > max) {
                    ans = i;
                    max = total;
                }
            }
            return total >= 0 ? ans : -1;
        }
    }
    

  • 0

    @gordonillan said in A simple T(n):S(1) solution:

    		Scan the list backwards and accumulate the cost difference. After the scan is complete, if the cumulative cost difference is >= 0, then the station with the highest cumulative cost difference is the place to start. Otherwise return -1.
    

    what is the logic behind this approach ?


Log in to reply
 

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