Introduction
This problem is one of the most asked problems and it comes under the array manipulation topic. So if you have a good grasp of the array, this should be a piece of cake.
I am going to discuss 2 approaches here: The brute Force and the Optimized approach.
Prompt
You are given an array prices where prices[i] is the price of a given stock on the i<sup>th</sup> 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 = [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4
//Note that before selling you need to buy a stock.
//Example 2:
Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transactions are done and the max profit = 0.
1) Brute Force Approach
const maxProfit = (prices) => {
let buy = Infinity, profit = 0
for (let i = 0; i < prices.length; i++) {
let temp = -Infinity
for (let j = i + 1; j < prices.length; j++) {
temp = prices[j] - prices[i]
profit = Math.max(profit, temp)
}
}
return profit
};
const prices = [7,1,5,3,6,4]
const res = maxProfit(prices)
console.log(res) // 5
The time complexity for this approach will be O(n^2) and the space complexity is O(1).
Note: This brute force approach will throw a time limit exceeded error in LeetCode.
2) Optimized Approach
const maxProfit = (prices) => {
let buy = Infinity, profit = 0
for (let i = 0; i < prices.length; i++) {
let current = prices[i] // current selling price
buy = Math.min(buy, current) // to calculate min buy value
let temp = current - buy // getting current profit
profit = Math.max(profit, temp) // to calculate max profit
}
return profit
};
const prices = [7,1,5,3,6,4]
const res = maxProfit(prices)
console.log(res) // 5
Ending Note
This is a classic array manipulation problem and is often asked during interviews.