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

Welcome to the start of the DP on Stocks series! Across various technical interviews, stock-based dynamic programming problems appear frequently. Mastering this curated sequence of six problems ensures you are fully prepared for any stock-related interview question. In this introductory chapter, we dissect the foundational first problem: Best Time to Buy and Sell Stock.

1. Why Do We Need This? (Problem Statement & Status Quo)

The Core Challenge

You are given an array representing the daily prices of a stock over $N$ consecutive days. Your goal is to maximize your financial profit by choosing a single day to buy the stock and a subsequent day to sell it.

• Constraint 1: You must buy the stock before you sell it. Time travel is impossible; you cannot buy in the future and sell in the past.
• Constraint 2: You are allowed to complete at most one transaction (one buy and one sell).
• Goal: Find the maximum possible profit. If no profit can be made (i.e., prices only decrease), the maximum profit should be 0.

Example Walkthrough

Consider an array of stock prices over 6 days:

Days:    [Day 1, Day 2, Day 3, Day 4, Day 5, Day 6]
Prices:  [  7  ,   1  ,   5  ,   3  ,   6  ,   4  ]

• Invalid Scenario: Buying on Day 1 (price = 7) and selling on Day 2 (price = 1) yields a negative profit (1 - 7 = -6), which is invalid because selling must occur after buying.
• Suboptimal Scenario: Buying on Day 2 (price = 1) and selling on Day 3 (price = 5) yields a profit of 5 - 1 = 4.
• Optimal Scenario: Buying on Day 2 (price = 1) and selling on Day 5 (price = 6) yields a profit of 6 - 1 = 5. This is the maximum achievable profit for this dataset.

2. Core Mental Model: The "Minimum on the Left" Principle

Real-Life Analogy

Imagine walking through a marketplace day by day with the goal of making the smartest investment. As you consider selling your stock on any given day, your natural instinct is: "I want to look back at all the previous days and figure out what the absolute lowest price was so I could have bought it at the cheapest possible rate."

Mathematical Intuition

If you decide to sell your stock on day $i$, to maximize your profit (Selling Price - Buying Price), you must minimize the buying price. Therefore, your ideal buying price is the minimum stock price found anywhere from Day $0$ up to Day $i - 1$.

3. Naive vs. Better Approach

The Naive Brute Force Approach

• Strategy: Use nested loops. For every day $i$ (as a selling day), iterate through all previous days $j$ (where $j < i$) to find the best buying price.
• Time Complexity: $O(N^2)$ due to the nested traversal.
• Space Complexity: $O(1)$.
• Why it fails in interviews: For large datasets, $O(N^2)$ is too slow. Interviewers expect an optimal linear scan.

The Optimized Linear Approach

• Strategy: Instead of looking backward with a nested loop on every step, maintain a running variable (mini) that tracks the minimum price encountered so far as you iterate through the array from left to right.
• Time Complexity: $O(N)$ because we traverse the array only once.
• Space Complexity: $O(1)$ because we only store a few variables (mini, profit, cost).

4. Step-by-Step Evolution of the Algorithm

Let's trace how the algorithm evaluates our example array prices = [7, 1, 5, 3, 6, 4] step-by-step:

1. Initialization:

   • Set mini = prices[0] (7)
   • Set maxProfit = 0

2. Iteration 1 (i = 1, price = 1):

   • Cost if sold today: price - mini = 1 - 7 = -6
   • Update maxProfit: max(0, -6) = 0
   • Update mini: min(7, 1) = 1 (since current price is smaller than mini)

3. Iteration 2 (i = 2, price = 5):

   • Cost if sold today: price - mini = 5 - 1 = 4
   • Update maxProfit: max(0, 4) = 4
   • Update mini: min(1, 5) = 1

4. Iteration 3 (i = 3, price = 3):

   • Cost if sold today: price - mini = 3 - 1 = 2
   • Update maxProfit: max(4, 2) = 4
   • Update mini: min(1, 3) = 1

5. Iteration 4 (i = 4, price = 6):

   • Cost if sold today: price - mini = 6 - 1 = 5
   • Update maxProfit: max(4, 5) = 5
   • Update mini: min(1, 6) = 1

6. Iteration 5 (i = 5, price = 4):

   • Cost if sold today: price - mini = 4 - 1 = 3
   • Update maxProfit: max(5, 3) = 5
   • Update mini: min(1, 4) = 1

• Final Answer: 5

5. Complete Code Implementation (C++)

Here is the clean, production-ready C++ implementation demonstrating the single-pass greedy/dynamic programming approach:

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int mini = prices[0];
        int maxProfit = 0;
        int n = prices.size();
        
        for(int i = 1; i < n; i++) {
            int cost = prices[i] - mini;
            maxProfit = max(maxProfit, cost);
            mini = min(mini, prices[i]);
        }
        
        OutputStream:
        return maxProfit;
    }
};

6. Connection to Dynamic Programming

Note: Why is this problem categorized under Dynamic Programming? Dynamic programming fundamentally relies on remembering the past to avoid redundant calculations. In this algorithm, the variable mini acts as our DP state memory—remembering the minimum sub-problem result (the lowest price seen so far from index 0 to i-1) as we advance through the array. While it can also be viewed as a greedy approach, it embodies the core state-transition philosophy of DP.

7. Real-World Practical Pitfalls & Edge Cases

When implementing or discussing this problem in an interview, keep these edge cases in mind:

• Strictly Decreasing Prices: (e.g., [7, 6, 4, 3, 1]). The algorithm correctly returns 0 because no profitable transaction can be made, and maxProfit is initialized to 0.
• Single Element Array: (e.g., [5]). The loop starting at i = 1 will be skipped entirely, and the function will correctly return 0.
• Duplicate Prices: (e.g., [2, 4, 2, 4]). The algorithm correctly evaluates the maximum span from the global minimum to subsequent peaks.

Summary and Key Takeaways

• Problem Goal: Maximize profit from a single buy-sell transaction given a daily stock price array.
• Temporal Constraint: Buying must always precede selling; no time travel or backward transactions allowed.
• Brute Force Inefficiency: Checking every possible buy-sell pair using nested loops yields an unacceptable $O(N^2)$ time complexity.
• Optimal Strategy: Maintain a running minimum (mini) of stock prices on the left while scanning the array once from left to right.
• Time Complexity: $O(N)$ as we traverse the array in a single pass.
• Space Complexity: $O(1)$ auxiliary space since only a few scalar variables are maintained.
• DP Connection: Remembering past minimums mirrors the core state-memoization principle of Dynamic Programming.
• Interview Readiness: This problem serves as the vital foundational stepping stone for the remaining 5 complex DP on Stocks problems.