:orphan:

Gas Station
===========

.. highlight:: none

Problem
-------
https://leetcode.com/problems/gas-station/

There are ``n`` gas stations along a circular route, where the amount of
gas at the ``i``\ :sup:```th``` station is ``gas[i]``.

You have a car with an unlimited gas tank and it costs ``cost[i]`` of
gas to travel from the ``i``\ :sup:```th``` station to its next
``(i + 1)``\ :sup:```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**.

 

**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 - 3 + 3 = 3
   You cannot travel back to station 2, as it requires 4 unit of gas but you only have 3.
   Therefore, you can't travel around the circuit once no matter where you start.

 

**Constraints:**

- ``n == gas.length == cost.length``
- ``1 <= n <= 10``\ :sup:```5```
- ``0 <= gas[i], cost[i] <= 10``\ :sup:```4```
- The input is generated such that the answer is unique.

.. highlight:: python

Pattern
-------
Array, Greedy

Solution
--------
Create a ``surplus`` array, which stores the difference between gas and cost.
If the sum of ``surplus`` is negative, then there is not enough gas to complete
the circuit no matter the starting point. Otherwise, we can complete the
circuit. Observe that if we cannot complete the circuit by ``i``, then we
cannot complete the circuit starting at any station in ``[start, i]``. This is
because the car had a non-empty tank until ``i``. Thus, if there is a solution,
it must be in ``[i + 1, n]``.

Code
----

.. literalinclude:: ../problems/medium/gas-station/gas_station__approach_1.py
    :language: python
    :lines: 13-

Test
----
>>> from gas_station__approach_1 import canCompleteCircuit
>>> gas = [1, 2, 3, 4, 5]
>>> cost = [3, 4, 5, 1, 2]
>>> canCompleteCircuit(gas, cost)
3
>>> gas = [2, 3, 4]
>>> cost = [3, 4, 3]
>>> canCompleteCircuit(gas, cost)
-1

Complexity
----------
| Time: :math:`O(n)` — single pass through stations
| Auxiliary Space: :math:`O(n)` — surplus array

.. autofunction:: gas_station__approach_1.canCompleteCircuit