Best Time to Buy and Sell Stocks

Problem Statement

LeetCode-121: 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.

Approach

Before we discuss the solution, here are a few observations:

1. To find the maximum profit, we need to find the minimum and maximum prices from the given input.
2. Assuming minimum price is found at index i maximum price at index j, we can use those to calculate the maximum result \( \iff j > i\). This is because we can only sell a stock at index \(j\), if we have purchased it in the past at index \(i \enspace | \enspace i < j\).
3. Once the above two points are clear, we can rephrase the problem such that it requires us to find the minimum and a future maximum value from the given input.
4. We do this by keeping a track of minimum value for every index \(i\) - let’s call this minPrice.
5. Similarly, we keep a track of maximum profit maxProfit by evaluating: \(max(maxProfit, currPrice - minPrice)\)

Implementation

The following is a java implementation of the above mentioned approach:

public int maxProfit(int[] prices) {
    int maxProfit = 0;
    int minPrice = prices[0];

    for(int currPrice : prices){
        // keep track of min price so far
        minPrice = Math.min(minPrice, currPrice);

        // maxProfit so far = max(maxProfit, currPrice - minPrice)
        maxProfit = Math.max(maxProfit, currPrice - minPrice);
    }   
    return maxProfit;
}

Complexity Analysis

With this approach, we are able to find a solution in \(O(n)\) time complexity.