Best Time to Buy and Sell Stock [Interview Question]

Problem
You are given an array prices where prices[i] is the price of a given stock on the ith day.

You need 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.

LeetCode Problem Link

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.

Best time to buy and sell stock solution

Approach

In this approach, we will find the largest number followed by the smallest number. We can maintain two variables – minBuyPrice and maxProfit corresponding to the smallest number and maximum profit (maximum difference between selling price and min-price) obtained so far respectively.

Pseudocode

1. minBuyPrice = 0, maxProfit = 0, setting minBuyPrice index to the starting of the array and maxProfit to zero.
2. Traverse the array prices (0 <= i < prices.size()):
3.   If prices[i] < prices[minBuyPrice]: 
4.     minBuyPrice = i
5.   profit = prices[i] - prices[minBuyPrice]
6.   if (profit > maxProfit): 
7.     maxProfit = profit
8.   return maxProfit

Time Complexity: O(n), where n is the size of prices array
Space complexity : O(1)

Code Implementation

class Solution {
public:

    int maxProfit(vector<int>& prices) {

        int profit=0, maxProfit=0, buy=0;
        
        for (int i=0; i<prices.size(); i++) {
            if (prices[i] < prices[buy]) {
                buy = i;
            }

            profit = prices[i] - prices[buy];

            if (profit > maxProfit) {
                maxProfit = profit;
            }
        }

        return maxProfit;
    }
};

Output

Your input
[7,1,5,3,6,4]
Output
5
Expected
5