[Amazon][LeetCode] Best Time to Buy and Sell Stock

Problem: 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.

Example:

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.

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transactions are done and the max profit = 0.

Approach: One way to do it is we can maintain an array leftMin where leftMin[i] will give the minimum value in the prices[0...i]. Similarly we can maintain an array rightMax where rightMax[i] will give the maximum of prices[i...n-1]. It is obvious that maximum of all the rightMax[i] - leftMin[i] where i = 0...n-1 will be our answer.

The above approach is a big optimiztion over brute force approach but it's still doing three iterations and moreover the space is 2*n. Let's try to do better.

Instead of maintaining rightMax array we can have a variable maxElement which gives at any ith index the maximum of prices[i...n-1] and then we can just return the max of maxElement - leftMin[i] for i = 0...n-1. See now we have just save n space and also we are saving one iteration.

If we see like maxElement, we can maintain a minElement which gives at ith index the min of pices[0...i], so now do we need to actually need to create any addition array? No right. Actually we don't need maxElement from right. At any i (i = 0...n-1), if we have Min(prices[0...i]) which is our minElement, we can say the max profit using prices[i] will be prices[i] - minElement so if we take max of all prices[i] - minElement for every i = 0...n-1 then we will have our answer.

That's all!

Implementation in C#:

Using left min array:

    public int MaxProfit(int[] prices)

    {

        int length = prices?.Length ?? 0;

        if (length <= 1)

        {

            return 0;

        }

        int[] leftMinArr = new int[length];

        leftMinArr[0] = prices[0];

        for (int i = 1; i < length; ++i)

        {

            leftMinArr[i] = Math.Min(leftMinArr[i - 1], prices[i]);

        }

        int maxElement = prices[length - 1];

        int maxProfit = Math.Max(0, maxElement - leftMinArr[length - 1]);

        for (int i = length - 2; i >= 0; --i)

        {

            maxElement = Math.Max(maxElement, prices[i]);

            maxProfit = Math.Max(maxProfit, maxElement - leftMinArr[i]);

        }

        return maxProfit;

    }

Without using extra space:

    public int MaxProfit(int[] prices)

    {

        int length = prices?.Length ?? 0;

        if (length <= 1)

        {

            return 0;

        }

        int minElement = prices[0];

        int maxProfit = 0;

        for (int i = 0; i < length; ++i)

        {

            minElement = Math.Min(minElement, prices[i]);

            maxProfit = Math.Max(maxProfit, prices[i] - minElement);

        }

        return maxProfit;

    }

Complexity: O(n)