Practice/Bloomberg/Leetcode 134. Gas Station

Leetcode 134. Gas Station

CodingOptional

Problem

You are planning a road trip around a circular route with n energy stations positioned along the way. At each station i, you can refuel your vehicle with energy[i] units of fuel. Traveling from station i to the next station (i+1) % n requires cost[i] units of fuel.

Your vehicle starts with an empty tank, and you want to determine if there exists a starting station from which you can complete the entire circular route exactly once, visiting all stations in clockwise order and returning to your starting point.

If such a starting station exists, return its index. If no valid starting station exists, return -1.

You may assume that if a solution exists, it is unique.

Requirements

1. Implement a function that takes two arrays: energy and cost
2. Return the index of the starting station if a valid route exists
3. Return -1 if completing the circuit is impossible from any starting station
4. The solution must handle the circular nature of the route (after station n-1 comes station 0)

Constraints

• 1 ≤ n ≤ 10⁵ where n is the length of both arrays
• 0 ≤ energy[i], cost[i] ≤ 10⁴
• Both arrays have the same length
• Aim for O(n) time complexity and O(1) space complexity

Examples

Example 1:

` Input: energy = [1, 2, 3, 4, 5], cost = [3, 4, 5, 1, 2] Output: 3 Explanation: Starting at station 3:

• Station 3: tank = 0 + 4 = 4, travel to station 4 (cost 1), tank = 3
• Station 4: tank = 3 + 5 = 8, travel to station 0 (cost 2), tank = 6
• Station 0: tank = 6 + 1 = 7, travel to station 1 (cost 3), tank = 4
• Station 1: tank = 4 + 2 = 6, travel to station 2 (cost 4), tank = 2
• Station 2: tank = 2 + 3 = 5, travel to station 3 (cost 5), tank = 0 Successfully completed the circuit! `

Example 2:

Input: energy = [2, 3, 4], cost = [3, 4, 3] Output: -1 Explanation: Total energy available is 9, but total cost is 10. It's impossible to complete the circuit regardless of starting point.

Example 3:

Input: energy = [5], cost = [4] Output: 0 Explanation: With only one station, you gain 5 units and spend 4 units to return to the same station. Station 0 works.