Gas Station Solution for Microsoft

Company: Microsoft · Difficulty: Medium · Topics: Array, Greedy

Problem Statement

There are n gas stations along a circular route, where the amount of gas at the ith station is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from the ith station to its next (i + 1)th station. You begin the journey with an empty tank at one of the gas stations.

Given two integer arrays gas and cost, return the starting gas station's index if you can travel around the circuit once in the clockwise direction, otherwise return -1. If there exists a solution, it is guaranteed to be unique.

Examples

Example 1:

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

Output: 3

Explanation:

Start at station 3 (index 3) and fill up with 4 unit of gas. Your tank = 0 + 4 = 4

Travel to station 4. Your tank = 4 - 1 + 5 = 8

Travel to station 0. Your tank = 8 - 2 + 1 = 7

Travel to station 1. Your tank = 7 - 3 + 2 = 6

Travel to station 2. Your tank = 6 - 4 + 3 = 5

Travel to station 3. The cost is 5. Your gas is just enough to travel back to station 3.

Therefore, return 3 as the starting index.

Example 2:

Input: gas = [2,3,4], cost = [3,4,3]

Output: -1

Explanation:

You can't start at station 0 or 1, as there is not enough gas to travel to the next station.

Let's start at station 2 and fill up with 4 unit of gas. Your tank = 0 + 4 = 4

Travel to station 0. Your tank = 4 - 3 + 2 = 3

Travel to station 1. Your tank = 3 - 4 + 3 = 2

You can't travel back to station 2, as it requires 3 unit of gas but you only have 2.

Therefore, you can't travel around the circuit once no matter where you start.

Example 3:

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

Output: 4

Explanation:

Start at station 4 (index 4) and fill up with 4 unit of gas. Your tank = 0 + 4 = 4

Travel to station 0. Your tank = 4 - 1 + 5 = 8

Travel to station 1. Your tank = 8 - 4 + 1 = 5

Travel to station 2. Your tank = 5 - 4 + 2 = 3

Travel to station 3. Your tank = 3 - 1 + 3 = 5

Travel to station 4. The cost is 5. Your gas is just enough to travel back to station 4.

Therefore, return 4 as the starting index.

Intuition

The key insight is that if the total gas available is less than the total cost, it's impossible to complete the circuit. If the total gas is greater than or equal to the total cost, there must be a solution.

The optimal approach is to:

1. Check if total gas >= total cost (if not, return -1)

2. Start from index 0 and keep track of current gas tank

3. If at any point the tank becomes negative, reset the starting point to the next station

4. Continue until we find a valid starting point

Approach

Approach 1: Greedy Algorithm (Optimal)

1. Calculate total gas and total cost

2. If total gas < total cost, return -1

3. Start from index 0, keep track of current tank

4. If tank becomes negative, reset start to next station and tank to 0

5. Return the starting index when we complete the circuit

Approach 2: Brute Force

1. Try starting from each station

2. For each starting point, simulate the complete journey

3. Return the first valid starting point or -1

Approach 3: Two Pass

1. First pass: find total gas and cost

2. Second pass: find the starting point using greedy approach

Dry Run

Let's trace through Example 1: gas = [1,2,3,4,5], cost = [3,4,5,1,2]

Greedy Approach:

Key Insights

1. Total Gas vs Total Cost: If total gas < total cost, no solution exists

2. Greedy Property: If we can't reach station j from station i, we can't reach j from any station between i and j

3. Single Pass: We only need one pass through the array to find the solution

4. Unique Solution: If a solution exists, it's guaranteed to be unique

Edge Cases

1. No Solution: Total gas < total cost

2. Single Station: Only one gas station

3. All Same: All gas stations have same gas and cost

4. Exact Match: Total gas equals total cost

Solutions

Best Approach: Greedy Algorithm

Average Approach: Two Pass

Worst Approach: Brute Force

More Microsoft coding questions