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
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 == ncost.length == n1 <= n <= 1050 <= 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
LeetCode Discussion:control_the_narrative
Note 1: Loop and Iteration
Note 2: Access an array item by its index
Note 3: Conditional (ternary) operator
Note 4: Addition assignment(+=)
Note 5: if statement
Blog Cover Image Credit
Top comments (2)
It's really great that you're documenting your learning process. It's a good way to stay motivated and motivate others as well! I love it!
:) thank you