Crack the Backend

Problem Statement

There are n gas stations on a circular route. gas[i] is the amount of gas you get at station i, and cost[i] is the cost to travel from station i to i+1 (with n-1 to 0 for the last segment). You have an empty tank initially. Return the starting gas station's index if you can travel around the circuit once (clockwise), otherwise -1. If a solution exists, it is unique.

Key Observations

Necessary condition: If sum(gas) < sum(cost), we cannot complete the circuit — return -1. Otherwise a solution exists.
Greedy: Start at index 0, maintain tank (current gas). For each i, add gas[i] - cost[i] to tank. If at some i the tank becomes negative, we cannot start at any index 0..i (each would fail at or before i+1). So we restart the candidate start at i+1 and reset tank to 0. After the loop, start is a valid starting index (and we've verified total gas >= total cost).

Approach

High-level: If sum(gas) < sum(cost) return -1. start=0, tank=0. For i=0..n-1: tank += gas[i]-cost[i]; if tank < 0 then start = i+1, tank = 0. Return start.

Steps: total=0, tank=0, start=0. For i: total += gas[i]-cost[i], tank += gas[i]-cost[i]; if tank<0 then start=i+1, tank=0. If total<0 return -1 else return start.

Implementation

Java

public int canCompleteCircuit(int[] gas, int[] cost) {
    int total = 0, tank = 0, start = 0;

    for (int i = 0; i < gas.length; i++) {
        total += gas[i] - cost[i];
        tank += gas[i] - cost[i];

        if (tank < 0) { start = i + 1; tank = 0; }
    }

    return total >= 0 ? start : -1;
}

Test Cases

Example 1

Input

gas = [1,2,3,4,5], cost = [3,4,5,1,2]

Expected

3

Explanation

Start at index 3.

Complexity Analysis

Time: typically O(n) or O(n log n).
Space: O(1) or O(n).

Follow-ups

Prove greedy choice property; handle ties.