Interview 150
Gas Station
- Problem
- LC 134
- File
- interview150_LC134GasStation.java
- Path
- pkg5leetcode/interview150/interview150_LC134GasStation.java
- Package
- pkg5leetcode.interview150
- Command
- java pkg5leetcode/interview150/interview150_LC134GasStation.java
- Approach
- Track total and running tank; start at index after deficit.
- Complexity
- Time O(n), Space O(1)
There is no in-browser runner. This is the file from the curriculum, unchanged.
1package pkg5leetcode.interview150;2 3/*4 * Gas Station | LC 1345 * APPROACH: Track total and running tank; start at index after deficit.6 * COMPLEXITY: Time O(n), Space O(1)7 */8public class interview150_LC134GasStation {9 static int canCompleteCircuit(int[] gas, int[] cost) {10 int total = 0, tank = 0, start = 0;11 for (int i = 0; i < gas.length; i++) {12 total += gas[i] - cost[i];13 tank += gas[i] - cost[i];14 if (tank < 0) { start = i + 1; tank = 0; }15 }16 return total >= 0 ? start : -1;17 }18 19 public static void main(String[] args) {20 check(canCompleteCircuit(new int[]{1, 2, 3, 4, 5}, new int[]{3, 4, 5, 1, 2}) == 3, "case1");21 check(canCompleteCircuit(new int[]{2, 3, 4}, new int[]{3, 4, 3}) == -1, "case2");22 System.out.println("all tests passed");23 }24 25 static void check(boolean cond, String name) {26 if (!cond) throw new AssertionError("FAILED: " + name);27 System.out.println(" PASS " + name);28 }29}