Leetcode: 121. Best Time to Buy and Sell Stock

• Pattern: Search for max/min value in unsorted array.
• Pattern: Problem's constraints disallow \(O(n^2)\) solutions.

• Can we solve the problem by iterating from left to right (or right to left)?

Suppose we know that the best day to buy is on \(i\)th day but we don't know when to sell the stock to maximize the profit. In this case, the problem becomes finding the index \(j\) where \(j > i\) and \(prices[j]-prices[i]\) is the maximum possible profit. The naive approach to find \(j\) consists on iterating over \(i+1,i+2,...,n-1\). While it solves the problem, this solution is \(O(n^2)\) and does not pass on all tests. Therefore, we have to come up with a more efficient way to find \(j\).

Without knowing any interesting property about \(prices\), we might have to use extra memory to efficiently find the index \(j\) (Improve Performance Using More Memory). Be \(f(i)\) the maximum value in \(prices[i,i+1,..,n-1]\). We can define \(f\) recursively as \(f(i)=max(prices[i], f(i+1))\). More, we can compute \(f\) by iterating over the input from right to left.

The problem of finding \(j\) became trivial if we use \(f\). We first compute \(f\) and them solve the original problem. Going back to the original problem, for each \(i\) it is possible to test if buying on \(i\)th day and selling for the price of \(f(i+1)\) is the best option. The algorithm has time and space complexity of \(O(n)\). Wait, we can do better than that! While we search for the best \(i\) from right to left, we can keep track of the last value of \(f(i+1)\) since this is the only interesting value when testing \(i\). This optimization will reduce the space complexity to \(O(1)\) making the solution more efficient.

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        ans, m = 0, float("-inf")
        for n in reversed(prices):
            ans = max(ans, m - n)
            m = max(m, n)
        return ans

• Interview preparation: V