buy-sell-stocks-i.md

Best Time to Buy and Sell Stock

Practice Link

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.

Intiution

Buy the stock at lowest price and sell it when price is highest.

Naive Approach

We can try to sell the stock every day and try to find the maximum profit that can be generated by selling the stock on that day. At last, we can return the maximum of these individual maximum profits as our answer.

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        int maxProfit = 0;
        for(int i=0;i<n-1;i++)
        {
            int buy = prices[i];
            for(int j=i+1;j<n;j++)
            {
                int sell = prices[j];
                maxProfit = max(maxProfit, sell-buy);
            }
        }
        return maxProfit;
    }
};

Time Complexity: O(n^2) --> TLE

Space Complexity: O(1)

Better Approach

To find the individual maximum profit on a day ‘i’, we know the selling price, i.e the price of the stock on day i, we need to find the buying price. To maximize the profit on day ‘i’, the buying price should be the lowest price of the stock from day 0 to day i.

This way we can keep track of the correct buying price for any day.

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int minPrice = prices[0];
        int maxProfit = 0;
        for(int i=1; i<prices.size(); i++)
        {
            if(prices[i] < minPrice)
                minPrice = prices[i];

            maxProfit = max(maxProfit, prices[i] - minPrice);
        }
        return maxProfit;
    }
};

Time Complexity: O(n)

Space Complexity: O(1)