Best Time to Buy and Sell Stock

Question 1 (LC.121)

Given an array of stock prices where prices[i] = stock price on day i, design an algorithm to find the maximum profit with one transaction.

You have to buy the stock before selling it.

Example

Input: [7, 1, 5, 3, 6, 4]
Output: 5 Buy at 1 and sell at 6

Analysis

The brute force solution is for each number find the potential max profit if make the purchase here. Nested loops so O(n^2). Alright so how do we get to linear time?

Approach

1. optimal subproblems
    maxProfit(n) = maximum profit you can get at day n
2. solve by prefix
    maxProfit(n) = Math.max(maxProfit(n-1), prices[n] - localMin)
3. topo order
    for i from 2 to n
4. base cases
    maxProfit(0) = 0
5. answer
    return maxProfit(n)

Code

public int maxProfit(int[] prices) {
    // edge cases
    if (prices == null || prices.length == 0) {
        return 0;
    }
    // create memo table
    int[] memo = new int[prices.length];
    // init base case
    memo[0] = 0;
    int localMin = prices[0];
    // topo order
    for (int i = 1; i < prices.length; i++) {
        localMin = Math.min(localMin, prices[i]);
        memo[i] = Math.max(memo[i-1], prices[i] - localMin);
    }
    // answer
    return memo[memo.length - 1];
}

Time & Space Complexity

Time: one loop so O(n) Space: store the partial answers to all subproblems so O(n)

Follow Up #1

Can you do Q1 in O(1) space?

Analysis

maxProfit(n) = Math.max(maxProfit(n-1), prices[n] - localMin) only needs the previous subproblem and localMin which we already have. We can just store the previous value in a variable.

Code

public int maxProfit(int[] prices) {
    // edge cases
    if (prices == null || prices.length == 0) {
        return 0;
    }
    // create memo table
    int profit;
    // init base case
    profit = 0;
    int localMin = prices[0];
    // topo order
    for (int i = 1; i < prices.length; i++) {
        localMin = Math.min(localMin, prices[i]);
        profit = Math.max(profit, prices[i] - localMin);
    }
    // answer
    return memo[memo.length - 1];
}

Time Complexity

Time: O(n) Space: O(1)

Question 2