O(n) runtime and O(1) space complexity with DP


  • 0
    G

    This problem can be gracefully solved with two pointers. It will take only O(n) runtime and constant space - since we only need three additional integers to compute the starting point. In this case, that's the best we can do.
    We only need one pass through the arrays.

    Here is my strategy:

    1. Go through both arrays at the same time and add gas[i] - cost[i] to your fuel tank. Additionally add the same value to a total fuel sum. We will need that at the end.
    2. As long as your fuel tank is bigger or equal zero, do not change the starting point (except it is currently not set). This means you actually are on a running trip with a valid starting point.
    3. When the fuel becomes empty, unset the starting point and reset your fuel tank to zero (it can only be zero, negative values make no sense here).
    4. After looping through the array, you finally have to check if it's possible at all to start from any point in the array. We can simply achieve this by checking if the total fuel is bigger or equal 0.

    If the total amount is bigger 0, we can use our currently valid starting point, otherwise there is no valid starting point.

    public int canCompleteCircuit(int[] gas, int[] cost) {
            if (gas == null || cost == null || gas.length == 0 || cost.length == 0) {
                return -1;
            }
            
            int fuel = 0;
            int start = -1;
            int total = 0;
            
            for (int i = 0; i < gas.length; i++) {
                fuel += gas[i] - cost[i];
                total += gas[i] - cost[i];
                if (fuel >= 0 && start == -1) {
                    start = i;
                } else if (fuel < 0) {
                    fuel = 0;
                    start = -1;
                }
            }
            
            if (total < 0) {
                start = -1;
            }
            
            return start;
        }
    

Log in to reply
 

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