Valid Starting City

Tags

Valid Starting City

Category

Greedy

Difficulty

Medium

Problem Statement

There are n cities arranged in a circular route. You are given arrays of fuel available at each city and distances between consecutive cities. Find the index of the valid starting city from which you can complete the full circular route without running out of fuel. The car starts with an empty tank. Exactly one valid starting city is guaranteed to exist.

Intuition

As you simulate the journey, the fuel balance (fuel gained minus fuel consumed) fluctuates. The valid starting city is the one immediately after the point where the cumulative fuel balance reaches its minimum. Starting there means you never encounter a negative balance during the trip. This works because the overall fuel is guaranteed to be sufficient; we just need to find the right starting point to avoid deficits.

Approach

  1. Initialize currentFuel = 0 and track the minimum cumulative fuel and the city index where it occurs.
  2. Iterate through all cities (0 to n - 1):
    • Add the fuel at the current city and subtract the distance to the next city.
    • If currentFuel is less than the tracked minimum, update the minimum and record the city index.
  3. The valid starting city is (minCity + 1) % n.

Pseudocode

function validStartingCity(distances, fuel, mpg):
    currentFuel = 0
    minFuel = 0
    minCity = 0

    for i from 0 to length(distances) - 1:
        currentFuel = currentFuel + fuel[i] - distances[i]
        if currentFuel < minFuel:
            minFuel = currentFuel
            minCity = i

    return (minCity + 1) % length(distances)

Time & Space Complexity

  • Time: O(n) where n is the number of cities. A single pass through the arrays.
  • Space: O(1). Only a few tracking variables are used.

Key Insights

  • The problem is equivalent to finding the starting point in a circular array where no prefix sum goes negative.
  • The city after the global minimum cumulative fuel balance is always the valid starting point.
  • This is the same principle behind the classic "gas station" problem.
  • If mpg (miles per gallon) is part of the problem, multiply fuel by mpg to get effective fuel.
  • The guarantee that exactly one valid starting city exists simplifies the problem (total fuel equals total distance).

Edge Cases

  • Only one city: it must be the starting city (distance to next is 0 or fuel covers it).
  • All fuel values equal all distance values: every city is valid, but we return the first found.
  • The minimum occurs at the last city: the valid starting city wraps around to city 0.
  • Very large or very small fuel/distance values: the algorithm handles them the same way since it only tracks cumulative differences.

Linked mentions