Your Web News in One Place

Help Webnuz

Referal links:

Sign up for GreenGeeks web hosting
February 25, 2022 03:05 am GMT

Day 13 of Studying LeetCode Solution until I Can Solve One on My Own: Problem134. Gas Station(Medium/JavaScript)

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: 3Explanation:Start at station 3 (index 3) and fill up with 4 unit of gas. Yourtank = 0 + 4 = 4Travel to station 4. Your tank = 4 - 1 + 5 = 8Travel to station 0. Your tank = 8 - 2 + 1 = 7Travel to station 1. Your tank = 7 - 3 + 2 = 6Travel to station 2. Your tank = 6 - 4 + 3 = 5Travel to station 3. The cost is 5. Your gas is just enough totravel back to station 3.Therefore, return 3 as the starting index.

Example 2:

Input: gas = [2,3,4], cost = [3,4,3]Output: -1Explanation:You can't start at station 0 or 1, as there is not enough gas totravel to the next station.Let's start at station 2 and fill up with 4 unit of gas. Your tank= 0 + 4 = 4Travel to station 0. Your tank = 4 - 3 + 2 = 3Travel to station 1. Your tank = 3 - 3 + 3 = 3You cannot travel back to station 2, as it requires 4 unit of gasbut you only have 3.Therefore, you can't travel around the circuit once no matterwhere 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
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


Original Link: https://dev.to/corndog_com567/day-13-of-studying-leetcode-solution-until-i-can-solve-one-on-my-own-problem134-gas-stationmediumjavascript-2fn5

Share this article:    Share on Facebook
View Full Article

Dev To

An online community for sharing and discovering great ideas, having debates, and making friends

More About this Source Visit Dev To