Gas Station

Description

https://leetcode.com/problems/gas-station/description/

Naive Solution — Traverse

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int length = gas.length;
        //traverse all the node on the circle.
        int start = 0;
        while(start < length) {
            if (validate(start, gas, cost) == true) return start;
            start += 1;
        }
        return -1;
    }
    
    public boolean validate(int start, int[] gas, int[] cost) {
        int length = gas.length;
        int remain = 0;
        int count = 0; 
        while(count <= length) {
            remain += gas[start];
            if (remain < cost[start]) return false; // Invalid position
            remain -= cost[start];
            start = (start + 1) % length;
            count += 1;
        }
        return true;  //The starter found;
        
    }
}

Faster Solution

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int length = gas.length;
        //traverse all the node on the circle.
        int start = 0;
        while(start < length) {
            int pos = validate(start, gas, cost);
            if (pos == -1) return start;
            if (pos > start) 
                start = pos;
            else
                //The inteval between start to end has no feasible position
                return -1;
        }
        return -1;
    }
    
    public int validate(int start, int[] gas, int[] cost) {
        int length = gas.length;
        int remain = 0;
        int count = 0; 
        while(count <= length) {
            remain += gas[start];
            if (remain < cost[start]) return (start + 1) % length; // Invalid position
            remain -= cost[start];
            start = (start + 1) % length;
            count += 1;
        }
        return -1;  //The starter found;
        
    }
}