Day 13 of Studying LeetCode Solution until I Can Solve One on My Own: Problem#134. Gas Station(Medium/JavaScript)
Published: 2022-02-25 03:05:41

**Intro:** I am a former accountant turned software engineer graduated from coding bootcamp in January 2022. Algorithms and Data Structure is an unavoidable part of interviews for most of the tech companies now. And one of my friends told me that you need to solve a medium leetcode problem under 60 seconds in order to get into the top tech companies.So I thought I'd start learning how to do it while job searching.

Since I have no clue on how to solve any of the problems (even the easy ones), I thought there is no point for me to waste hours and can't get it figured out. **Here is my approach:**
- Pick a leetcode problem randomly or Online Assessment from targeted companies.
- Study 1-2 solutions from Youtube or LeetCode discussion section. One brute force solution, another one more optimal.
- Write a blog post with detailed explanation and do a verbal walk through to help understand the solutions better.
- Code out the solution in LeetCode without looking at the solutions
- **Combat the forgetting curve:** Re-do the question for the next three days. And come back regularly to revisit the problem.

******************************************

**134. Gas Station**
`Difficulty: Medium` `Language: JavaScript` 
<!--IBM Backend Developer OA-->

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.**

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:
- `gas.length == n`
- `cost.length == n`
- `1 <= n <= 105`
- `0 <= gas[i], cost[i] <= 104`

******************************************

**Solution:**
```
var canCompleteCircuit = function(gas, cost) {
    
    let start = 0, tank = 0, total = 0

//set up a start variable to store the starting gas station's
//index if you can travel around the circuit once in the clockwise
//direction

//set up a tank variable to store remaing gas everytime we get to
//a new station, if tank is already less than 0. We will move on
//to the next starting index.

//set up a total variable, when it is positive, it means there is
//enough gas to over all the previous path.
    
    for (let i = 0; i < gas.length; i++){

//Loop (note 1) through each station to find the working starting
//station

        const usage = gas[i] - cost[i]

//calculation usage by subtracting the cost to get to the next
//station from added gas.

        tank += usage

//Update tank with usage data (note 4)
        
        if(tank < 0){
            tank = 0
            start = i + 1
        }

//if (note 5) tank is less than 0, means the starting station does
//not work. We will move on to the next starting station and reset
//the tank to 0.
        
        total += usage
    }
    
    return total < 0 ? -1 : start

//if total is less than 0 (note 3), that means there is not enough
//gas to get through all the station.But if it's more than 0,
//return the stating point that works.
    
};
```
**Solution Submission detail as of 2/24/2022** 
(Data below could vary since there are new tests/submissions daily)
- Runtime: 60 ms
- Memory Usage: 51.8 mb

******************************************

**References:**
[LeetCode Problem Link](https://leetcode.com/problems/gas-station/)
[LeetCode Discussion:control_the_narrative](https://leetcode.com/problems/gas-station/discuss/1019297/JavaScript-Clean-One-pass)
[Note 1: Loop and Iteration](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Guide/Loops_and_iteration)
[Note 2: Access an array item by its index](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array#access_an_array_item_by_its_index)
[Note 3: Conditional (ternary) operator](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Operators/Conditional_Operator)
[Note 4: Addition assignment(+=)](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Operators/Addition_assignment)
[Note 5: if statement](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Statements/if...else)
[Blog Cover Image Credit](https://www.istockphoto.com/portfolio/monsitj?mediatype=photography)