134. Gas station

134_solution1.c

int canCompleteCircuit(int *gas, int gasSize, int *cost, int costSize) {
  (void)costSize;
  int sumGas = 0, sumCost = 0;
  for (int i = 0; i < gasSize; i++) {
    sumGas += gas[i];
    sumCost += cost[i];
  }

  if (sumCost > sumGas)
    return -1;

  int start = 0, curGas = 0, curPos = 0;
  for (;;) {
    curGas += gas[curPos] - cost[curPos];

    curPos = (curPos + 1) % gasSize;

    if (curPos == start)
      return start;

    if (curGas < 0) {
      start = curPos;
      curGas = 0;
    }
  }
}

134_solution2.c

int canCompleteCircuit(int *gas, int gasSize, int *cost, int costSize) {
  (void)costSize;
  int total = 0, cur = 0, start = 0;
  for (int i = 0; i < gasSize; i++) {
    int diff = gas[i] - cost[i];
    total += diff;
    cur += diff;
    if (cur < 0) {
      start = i + 1;
      cur = 0;
    }
  }
  return total < 0 ? -1 : start;
}

134_solution1.cpp

#include <vector>

using namespace std;

class Solution {
public:
  int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
    int sumgas = 0, sumcost = 0;
    for (int i = 0; i < gas.size(); i++) {
      sumgas += gas[i];
      sumcost += cost[i];
    }

    if (sumcost > sumgas)
      return -1;

    int start = 0, curGas = 0, curPos = 0;
    for (;;) {
      curGas += gas[curPos];
      curGas -= cost[curPos];

      curPos++;
      curPos = curPos % gas.size();

      if (curPos == start)
        return start;

      if (curGas < 0) {
        start = curPos;
        curGas = 0;
      }
    }
  }
};

134_solution2.cpp

#include <vector>

using namespace std;

class Solution {
public:
  int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
    int total = 0, cur = 0, start = 0;
    for (int i = 0; i < gas.size(); i++) {
      int diff = gas[i] - cost[i];
      total += diff;
      cur += diff;
      if (cur < 0) {
        start = i + 1;
        cur = 0;
      }
    }
    return total < 0 ? -1 : start;
  }
};

134_solution1.go

package greedy

func canCompleteCircuit(gas []int, cost []int) int {
    sumGas, sumCost := 0, 0
    for i := range gas {
        sumGas += gas[i]
        sumCost += cost[i]
    }

    if sumCost > sumGas {
        return -1
    }

    start, curGas, curPos := 0, 0, 0
    for {
        curGas += gas[curPos] - cost[curPos]

        curPos = (curPos + 1) % len(gas)

        if curPos == start {
            return start
        }

        if curGas < 0 {
            start = curPos
            curGas = 0
        }
    }
}

134_solution2.go

package greedy

func canCompleteCircuit(gas []int, cost []int) int {
    total, cur, start := 0, 0, 0
    for i := range gas {
        diff := gas[i] - cost[i]
        total += diff
        cur += diff
        if cur < 0 {
            start = i + 1
            cur = 0
        }
    }
    if total < 0 {
        return -1
    }
    return start
}

134_solution1.java

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int sumGas = 0, sumCost = 0;
        for (int i = 0; i < gas.length; i++) {
            sumGas += gas[i];
            sumCost += cost[i];
        }

        if (sumCost > sumGas)
            return -1;

        int start = 0, curGas = 0, curPos = 0;
        for (;;) {
            curGas += gas[curPos] - cost[curPos];

            curPos = (curPos + 1) % gas.length;

            if (curPos == start)
                return start;

            if (curGas < 0) {
                start = curPos;
                curGas = 0;
            }
        }
    }
}

134_solution2.java

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int total = 0, cur = 0, start = 0;
        for (int i = 0; i < gas.length; i++) {
            int diff = gas[i] - cost[i];
            total += diff;
            cur += diff;
            if (cur < 0) {
                start = i + 1;
                cur = 0;
            }
        }
        return total < 0 ? -1 : start;
    }
}

134_solution1.js

/**
 * @param {number[]} gas
 * @param {number[]} cost
 * @return {number}
 */
var canCompleteCircuit = function (gas, cost) {
  const sumGas = gas.reduce((a, b) => a + b, 0);
  const sumCost = cost.reduce((a, b) => a + b, 0);
  if (sumCost > sumGas) return -1;

  let start = 0,
    curGas = 0,
    curPos = 0;
  for (;;) {
    curGas += gas[curPos] - cost[curPos];

    curPos = (curPos + 1) % gas.length;

    if (curPos === start) return start;

    if (curGas < 0) {
      start = curPos;
      curGas = 0;
    }
  }
};

134_solution2.js

/**
 * @param {number[]} gas
 * @param {number[]} cost
 * @return {number}
 */
var canCompleteCircuit = function (gas, cost) {
  let total = 0,
    cur = 0,
    start = 0;
  for (let i = 0; i < gas.length; i++) {
    const diff = gas[i] - cost[i];
    total += diff;
    cur += diff;
    if (cur < 0) {
      start = i + 1;
      cur = 0;
    }
  }
  return total < 0 ? -1 : start;
};

134_solution1.py

from typing import List


class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        if sum(cost) > sum(gas):
            return -1

        start = cur_gas = cur_pos = 0
        while True:
            cur_gas += gas[cur_pos] - cost[cur_pos]

            cur_pos = (cur_pos + 1) % len(gas)

            if cur_pos == start:
                return start

            if cur_gas < 0:
                start = cur_pos
                cur_gas = 0

134_solution2.py

from typing import List


class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        total = cur = start = 0
        for i in range(len(gas)):
            diff = gas[i] - cost[i]
            total += diff
            cur += diff
            if cur < 0:
                start = i + 1
                cur = 0
        return -1 if total < 0 else start

134_solution1.rs

impl Solution {
    pub fn can_complete_circuit(gas: Vec<i32>, cost: Vec<i32>) -> i32 {
        let sum_gas: i32 = gas.iter().sum();
        let sum_cost: i32 = cost.iter().sum();
        if sum_cost > sum_gas {
            return -1;
        }

        let (mut start, mut cur_gas, mut cur_pos) = (0, 0, 0);
        loop {
            cur_gas += gas[cur_pos] - cost[cur_pos];

            cur_pos = (cur_pos + 1) % gas.len();

            if cur_pos == start {
                return start as i32;
            }

            if cur_gas < 0 {
                start = cur_pos;
                cur_gas = 0;
            }
        }
    }
}

134_solution2.rs

impl Solution {
    pub fn can_complete_circuit(gas: Vec<i32>, cost: Vec<i32>) -> i32 {
        let (mut total, mut cur, mut start) = (0, 0, 0);
        for i in 0..gas.len() {
            let diff = gas[i] - cost[i];
            total += diff;
            cur += diff;
            if cur < 0 {
                start = i + 1;
                cur = 0;
            }
        }
        if total < 0 { -1 } else { start as i32 }
    }
}