134. Gas Station Medium

1/**
2 * [134] Gas Station
3 *
4 * There are n gas stations along a circular route, where the amount of gas at the i^th station is gas[i].
5 * You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from the i^th station to its next (i + 1)^th station. You begin the journey with an empty tank at one of the gas stations.
6 * 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
7 *  
8 * Example 1:
9 * 
10 * Input: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
11 * Output: 3
12 * Explanation:
13 * Start at station 3 (index 3) and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
14 * Travel to station 4. Your tank = 4 - 1 + 5 = 8
15 * Travel to station 0. Your tank = 8 - 2 + 1 = 7
16 * Travel to station 1. Your tank = 7 - 3 + 2 = 6
17 * Travel to station 2. Your tank = 6 - 4 + 3 = 5
18 * Travel to station 3. The cost is 5. Your gas is just enough to travel back to station 3.
19 * Therefore, return 3 as the starting index.
20 * 
21 * Example 2:
22 * 
23 * Input: gas = [2,3,4], cost = [3,4,3]
24 * Output: -1
25 * Explanation:
26 * You can't start at station 0 or 1, as there is not enough gas to travel to the next station.
27 * Let's start at station 2 and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
28 * Travel to station 0. Your tank = 4 - 3 + 2 = 3
29 * Travel to station 1. Your tank = 3 - 3 + 3 = 3
30 * You cannot travel back to station 2, as it requires 4 unit of gas but you only have 3.
31 * Therefore, you can't travel around the circuit once no matter where you start.
32 * 
33 *  
34 * Constraints:
35 * 
36 * 	n == gas.length == cost.length
37 * 	1 <= n <= 10^5
38 * 	0 <= gas[i], cost[i] <= 10^4
39 * 
40 */
41pub struct Solution {}
42
43// problem: https://leetcode.com/problems/gas-station/
44// discuss: https://leetcode.com/problems/gas-station/discuss/?currentPage=1&orderBy=most_votes&query=
45
46// submission codes start here
47
48impl Solution {
49    pub fn can_complete_circuit(gas: Vec<i32>, cost: Vec<i32>) -> i32 {
50        0
51    }
52}
53
54// submission codes end
55
56#[cfg(test)]
57mod tests {
58    use super::*;
59
60    #[test]
61    fn test_134() {
62    }
63}
64