Coding Interview — Stocks 101 (Array)
When to buy/sell the stock? Given an array contains the daily price for a stock. Try to find the maximum profit.
Input: [20,10,30,44,26,40,50]
Output: 58
Explanation:
Buy on day 2 and sell on day 4, profit = 44-10 = 34.
Buy on day 5 and sell on day 7, profit = 50-26 = 24.Thought process:
From previous question Move Zeros, we know that at least we want to loop through the input array once, so the Time Complexity would be O(n). We can use an additional data structure (i.e. Array/Linked List/Map/Set) to help us storing the day-to-day profit, and sum the profits at the end. But wait a second, do we really care about which day we make how much profit? Or can we just sum up the total profit while looping through the input array?
Solution:
makeProfit(prices) { // Use a constant space O(1) to record total profit.
let profit = 0; // While looping through the input array, we calculate the profit and add it to the sum.
for(let i = 0; i < prices.length - 1; i++) {
profit += Math.max(0, prices[i + 1] - prices[i]);
}
return profit;
};
Key Notes:
- Save Space
- How to track & calculate the profit from the input array?
What’s the next question?
Find Duplicates — Given an array of numbers, return true if any number appears more than once in the array, otherwise return false. (thought process and solution)
Before You Go —
There’s no better way to support me than to give me a follow on Medium (Victor Lin). Let me know that I should write more!
Did you know that you can give up to 50 👏’s by pressing down on the 👏 button? Give it a try if you reeeeeeally liked this article!
