DP 35. Best Time to Buy and Sell Stock | DP on Stocks

The Best Time to Buy and Sell Stock problem marks the foundation of the 6-part "DP on Stocks" series. It establishes the foundational principle of dynamic programming: leveraging past states (the minimum price seen so far) to make optimal local decisions on each prospective selling day.

1. Introduction to the "DP on Stocks" Series

The dynamic programming module on stock trading consists of six classic interview problems. Each problem introduces an additional constraint or dimension (e.g., single transaction, infinite transactions, at most $K$ transactions, transaction fees, and cooldown periods).

Note: In technical interviews, interviewers expect space-optimized solutions for stock problems. Understanding state transitions sequentially ensures complete mastery over the state space.

2. Problem Statement & Rules

You are given an array prices of size $N$, where prices[i] represents the price of a given stock on day $i$.

Transaction Rules

1. Single Transaction Constraint: You are permitted to complete at most one transaction (i.e., buy one share and sell one share).
2. Temporal Order Requirement: You cannot sell a stock before you buy it. If you sell on day $i$, you must have bought it on some day $j$ such that $j < i$.
3. Objective: Maximize the total profit:

4. No Loss Policy: If no positive profit can be achieved, return 0 (i.e., you do not execute any transaction).

3. Core Mental Model: The Prospective Selling Day

The core insight revolves around fixing the selling day and determining the optimal buying day:

Core Principle: If you decide to sell the stock on day $i$, to maximize profit you must have bought the stock at the absolute minimum price occurring between day $0$ and day $i - 1$.

Index:       0     1     2     3     4     5
Prices:    [ 7,    1,    5,    3,    6,    4 ]
                   ^                 ^
                   |                 |
               Best Buy           Best Sell
              (Price: 1)         (Price: 6)

Profit = 6 - 1 = 5

The Invariant

For every index $i$ from $1$ to $N-1$:

• $\text{minimal} = \min(\text{prices}[0 \dots i-1])$
• $\text{current\_profit} = \text{prices}[i] - \text{minimal}$
• $\text{max\_profit} = \max(\text{max\_profit}, \text{current\_profit})$

4. Naive vs. Optimal Approach

Why This is Dynamically Programmed

Dynamic Programming fundamentally means remembering past subproblem solutions to solve future ones. Here, we maintain a running summary of past states (mini) to evaluate each new state in $O(1)$ time rather than rescanning the prefix.

5. Step-by-Step State Evolution (Dry Run)

Consider the array: prices = [7, 1, 5, 3, 6, 4]

State Trace Table

Final Result: maxProfit = 5 (Buy on Day 1 at price 1, Sell on Day 4 at price 6).

6. Algorithmic Workflow

7. Multi-Language Implementation

C++

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        if (n == 0) return 0;

        int mini = prices[0];
        int maxProfit = 0;

        for (int i = 1; i < n; i++) {
            int cost = prices[i] - mini;
            maxProfit = max(maxProfit, cost);
            mini = min(mini, prices[i]);
        }

        return maxProfit;
    }
};

Java

public class Solution {
    public int maxProfit(int[] prices) {
        if (prices.length == 0) return 0;

        int mini = prices[0];
        int maxProfit = 0;

        for (int i = 1; i < prices.length; i++) {
            int cost = prices[i] - mini;
            maxProfit = Math.max(maxProfit, cost);
            mini = Math.min(mini, prices[i]);
        }

        return maxProfit;
    }
}

Python

class Solution:
    def maxProfit(self, prices: list[int]) -> int:
        if not prices:
            return 0
            
        mini = prices[0]
        max_profit = 0

        for i in range(1, len(prices)):
            cost = prices[i] - mini
            max_profit = max(max_profit, cost)
            mini = min(mini, prices[i])

        return max_profit

8. Complexity Analysis

• Time Complexity: $\mathcal{O}(N)$
  • A single linear loop processes each element of the array from index $1$ to $N-1$ exactly once. Each iteration performs $O(1)$ arithmetic and comparison operations.
• Space Complexity: $\mathcal{O}(1)$
  • Only two scalar variables (mini and maxProfit) are allocated to maintain state across iterations.

9. Edge Cases & Practical Pitfalls

• Strictly Decreasing Prices (e.g., [7, 6, 4, 3, 1]):
  • No profit can ever be realized (cost is always $\le 0$).
  • Initializing maxProfit = 0 guarantees the algorithm outputs 0 without requiring conditional branch overrides.
• Single Element Array (e.g., [5]):
  • The loop does not execute; returns 0 directly as no buy-sell pair exists.
• Identical Prices (e.g., [3, 3, 3, 3]):
  • cost = 3 - 3 = 0, yielding maximum profit 0.

10. Summary and Key Takeaways

• Single Transaction Constraint: At most one purchase and one sale are permitted; buying must precede selling.
• Selling Day Pivot: For any prospective selling day $i$, the maximum profit is achieved by buying at the minimum price in the range $[0, i-1]$.
• Dynamic Memory via Running Variable: Maintaining mini during a linear scan preserves optimal past history in $O(1)$ space, avoiding an $O(N^2)$ brute-force re-evaluation.
• Time and Space Efficiency: Achieves optimal $\mathcal{O}(N)$ runtime with strictly $\mathcal{O}(1)$ auxiliary memory.
• Gateway Problem: Serves as the base transition problem leading into multi-transaction DP states (Buy/Sell states, cooldowns, and transaction fee constraints).