Clean Java O(n) solution


  • 0
    public int canCompleteCircuit(int[] gas, int[] cost) {
      int pos = -1, curr = 0, total = 0;
      
      for (int i = 0; i < gas.length; i++) {
        int diff = gas[i] - cost[i];
        
        curr += diff; 
        total += diff;
        
        if (curr < 0) {
          // use up all the gas in current run
          // reset from the next one
          curr = 0;
          pos = i;
        }
      }
      
      if (total >= 0) return pos + 1;
      
      return -1;
    }

  • 0
    P

    Complex Solution:

    public int canCompleteCircuit(int[] gas, int[] cost) {
        int tag = 0;
        int tank = gas[0] - cost[0];
        int cur = 0;
        int circle = 0;
        while (true) {
            cur++;
            if (cur >= gas.length) {
                cur = 0;
                circle++;
            }
            if (cur == tag) {
                if (tank >= 0) {
                    return tag;
                } else {
                    return -1;
                }
            }
            if (tank < 0) {
                if (circle >= 1) {
                    return -1;
                } else {
                    tag = cur;
                    tank = 0;
                }
            }
            tank += gas[cur];
            tank -= cost[cur];
        }
    }
    

  • 0
    A
    This post is deleted!

Log in to reply
 

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