Best Time to Buy and Sell Stock
Say you have an array for which the
ithelement is the price of a given stock on dayi. If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit. Note that you cannot sell a stock before you buy one.
Time Complexity
- Brute Force: O(n²)
- Optimized: O(n)
Space Complexity
- Brute Force: O(1)
- Optimized: O(1)
Brute Force Approach
The brute force approach for this problem would be to calculate the profit for every possible pair of buy and sell days and keep track of the maximum profit. This would require nested loops and has a time complexity of O(n²).
Optimized Approach
The optimized approach involves maintaining variables for the minimum price and the maximum profit we’ve seen so far as we iterate through the array. The idea is to calculate the profit for every day assuming we sell on that day. We update our maximum profit and minimum price so far for each day. This approach only requires a single pass, making it much more efficient.
/**
* @param {number[]} prices
* @return {number}
*/
const maxProfit = (prices) => {
// Initializing the minPrice with the largest possible number in JavaScript
let minPrice = Number.MAX_VALUE;
// Initializing the maxProfit to 0 because the lowest profit you can make is 0 (i.e., you don't make any transaction)
let maxProfit = 0;
// Iterating over the array of prices
for (let i = 0; i < prices.length; i++) {
// The price of the stock on the current day
const currentPrice = prices[i]
// The profit if we sell the stock on the current day
const currentProfit = currentPrice - minPrice
// If the current price is less than the minimum price we've seen so far, update the minPrice
if (currentPrice < minPrice) {
minPrice = currentPrice;
}
// If the profit we can make by selling the stock on the current day is more than the maximum profit
// we've seen so far, update the maxProfit
if (currentProfit > maxProfit) {
maxProfit = currentProfit;
}
}
// At the end of the loop, maxProfit will hold the maximum profit we can make by buying and selling the stock
return maxProfit;
// Test cases
// maxProfit([7, 1, 5, 3, 6, 4]); // 5
// maxProfit([7, 6, 4, 3, 1]); // 0
// maxProfit([2, 4, 1]); // 2
// maxProfit([2, 1, 2, 1, 0, 1, 2]); // 2
// maxProfit([3, 2, 6, 5, 0, 3]); // 4
};Both the brute force and optimized solutions are in place, as they don’t use extra space that scales with input size. The optimized solution is more efficient and preferred over the brute force approach in this case.