This content originally appeared on DEV Community and was authored by DEV Community
Intro: I am a former accountant turned software engineer graduated from coding bootcamp. 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.
121. Best Time to Buy and Sell Stock
Difficulty: Easy Language: JavaScript
You are given an array prices where prices[i] is the price of a given stock on the ith day.
You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.
Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.
Example 1:
Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price =
6), profit = 6-1 = 5.
Note that buying on day 2 and selling on day 1 is not allowed
because you must buy before you sell.
Example 2:
Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transactions are done and the max
profit = 0.
Constraints:
1 <= prices.length <= 1050 <= prices[i] <= 104
Solution:
My first though is to find all possible profits and get the max profit with two for loops, but that exceeds the time limit. Key to solve this problem is understanding that stock can only be sold after it's bought. We will set the prices on day one as purchase and loop through the prices array:
- If a higher price is seem on the next day, save profit made by subtracting purchase price from the higher price. Note that the profit will be constantly updated whenever a new higher profit is found.
- If a lower price is seem on the next day, set it as the new puchase price. Note the purchase price variable will be constantly updated whenever a new lower price is seem.
- When the loop ends, the final profit is our answer.
var maxProfit = function(prices) {
let purchase = prices[0]
let profit = 0
//set initial profit as 0 and the prices on day one (note 2) as
//puchase price
for(let i = 1; i < prices.length; i++){
//Loop (note 1) prices array starting on index 1 as index 0 is
//already set as purchase price.
if(prices[i] < purchase){
purchase = prices[i]
//If (note 3) a lower price is seem on the next day, set it as the
//new puchase price.
} else profit = Math.max(profit, prices[i] - purchase)
//If a higher price is seem on the next day, save profit made by
//subtracting purchase price from the higher price.Note that the
//profit will be constantly updated (note 4) whenever a new higher
//profit is found.
}
return profit
};
References:
LeetCode Problem Link
Youtube: ThinkFWD
Note 1: For Loop
Note 2: Access an array item by its index
Note 3: if...else
Note 4: Math.max()
Blog Cover Image Credit
This content originally appeared on DEV Community and was authored by DEV Community
DEV Community | Sciencx (2022-03-06T20:19:55+00:00) Day 25 of Studying LeetCode Solution until I Can Solve One on My Own: Problem#121. Best Time to Buy and Sell Stock(Easy/JS). Retrieved from https://www.scien.cx/2022/03/06/day-25-of-studying-leetcode-solution-until-i-can-solve-one-on-my-own-problem121-best-time-to-buy-and-sell-stockeasy-js-2/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.