Best Time to Buy and Sell Stock Algorithm Solutions

The Best Time to Buy and Sell Stock problem encompasses multiple variants where you must determine optimal buying and selling points to maximize profit under various constraints like transaction limits, cooldown periods, or single vs. multiple transactions.

1. Pattern Restatement

Clarifying questions to ask the interviewer:

1. Can the input array be mutated, or should I preserve the original?
2. What is the expected return format — just the max profit, or also the buy/sell days?
3. Are there any constraints on input size (e.g., up to 10⁵ elements)?
4. Can there be duplicate prices, and should I handle that case?
5. What's the target complexity — O(n) time is expected, but what about space?

Restate the pattern or problem type in your own words: This is a classic single-pass optimization problem where we're given a sequence of stock prices and need to find the maximum profit achievable by buying and selling once, with the constraint that we must buy before we sell.

Clarify the signal words and constraint shape that point to it: Signal words include "buy and sell," "maximum profit," "single transaction," and "time series data." The constraint shape is that we have a linear sequence of values with ordering dependencies (buy before sell), making it amenable to single-pass optimization.

Note any assumptions you are making: I'm assuming that the input array contains at least two elements (since we need at least one buy and one sell to make a profit). I'm also assuming that the input array represents prices in chronological order.

Identify whether the pattern is best suited for static, streaming, or online scenarios if relevant: This pattern is best suited for static scenarios where the entire price sequence is available upfront. It's not naturally suited for streaming data since we need to know future prices to make optimal decisions, though a variant could be adapted for online scenarios with additional constraints.

The core insight is that we can solve this in one pass by tracking the minimum price seen so far and computing potential profits at each step, leveraging the constraint that we must buy before we sell.

2. When to Use This Pattern

Signal words and constraint shapes:

• "Buy and sell stock" or "maximize profit" problems
• Array of prices where you can only buy once and sell once
• Time series data with a single transaction allowed
• "Maximum difference between two elements where the smaller element comes before the larger one"

Why this pattern fits better than alternatives: This is fundamentally a single-pass optimization problem that benefits from maintaining running state. Unlike sliding window problems (which might consider multiple transactions) or dynamic programming approaches that build up solutions, this pattern leverages the constraint that we can only make one transaction. The key insight is that we don't need to check all possible pairs — we can maintain the minimum price seen so far and compute maximum profit at each step.

When variations apply instead:

• If multiple transactions are allowed, we'd use a greedy approach or DP with state transitions
• If we can buy and sell multiple times, we'd look for peaks and valleys in the price array
• If we have a transaction fee or cooldown period, we'd need more complex state tracking

Core insight: The optimal solution requires only one pass through the data because at each point, we only care about:

1. The minimum price seen so far (best buying opportunity)
2. The maximum profit achievable at the current point (best selling opportunity)

This makes it a perfect candidate for linear-time single-pass algorithms where we maintain invariants about optimal substructure.

## 3. Approach Evolution

**Interview communication script:**

"My first instinct is to solve this with a brute force approach where I check every possible buy-sell pair, which would give me O(n²) time complexity. But that's inefficient because I'm recalculating the same information repeatedly. Let me think about how to optimize this...

I notice that for any given day, I only need to know what the minimum price was up to that point to calculate the maximum profit. If I maintain a running minimum price as I iterate through the array, then for each day I can compute the maximum profit by subtracting that minimum from today's price. This reduces the problem to a single pass.

The key insight is that I don't need to look ahead or behind - for each day, the best profit I can make is with the lowest price seen so far. So if I keep track of the minimum price encountered and the maximum profit achievable, I can solve this in one pass.

Let me formalize this: I'll iterate through prices once, maintaining two variables - the minimum price seen so far and the maximum profit possible. For each day, I update these values if I find a new minimum price or a better profit."

**Brute-force approach and why it is not ideal:**

The brute force approach would involve checking every possible buy-sell pair by iterating through all combinations of indices where i < j. For each pair (i,j), we'd calculate profit = prices[j] - prices[i]. This requires nested loops and results in O(n²) time complexity, which becomes prohibitively slow for large inputs.

**Improved approach and the key optimization:**

The key optimization is recognizing that we only need to track two pieces of information as we iterate through the array:
1. The minimum price seen so far (this represents the best buying opportunity up to current day)
2. The maximum profit achievable at any point (this represents the best transaction so far)

By maintaining these invariants, we can compute the optimal solution in a single pass.

**Final approach with step-by-step reasoning:**

1. Initialize minimum price to first element and maximum profit to 0
2. Iterate from second element onwards:
   - Calculate potential profit by selling at current price with minimum price as buy price
   - Update maximum profit if this potential profit is better
   - Update minimum price if current price is lower than previous minimum
3. Return maximum profit

The invariants that must hold:
- Minimum price is always the lowest price seen so far in the array
- Maximum profit represents the best possible transaction up to current point
- We never sell before buying (ensures valid transactions)

**Important invariants that must hold:**

1. The minimum price variable always contains the lowest price encountered up to the current index
2. The maximum profit variable always contains the best profit achievable with a valid buy-sell pair up to current index
3. We never consider selling before buying, ensuring all transactions are valid

## 4. Data Structure Choice

For the Best Time to Buy and Sell Stock problem, I'll use a minimal set of variables to track the essential state needed for the optimal solution.

**Primary Data Structures:**

1. **Integer variables `minPrice` and `maxProfit`** - These are the core data structures needed for the optimal O(n) solution. We maintain:
   - `minPrice`: The lowest price seen so far (best buying opportunity)
   - `maxProfit`: The maximum profit achievable at each step

**Why These Data Structures:**
- **`minPrice`**: This is the key insight - we only need to track the minimum price seen so far, not all historical prices. This allows us to calculate the maximum profit at each step by simply comparing `currentPrice - minPrice` with our existing maxProfit.
- **`maxProfit`**: This accumulates the best possible profit we've seen so far, allowing us to return the optimal result at the end.

**Time and Space Impact:**
- **Time Complexity**: O(1) additional space - we only use a constant number of variables regardless of input size
- **Space Complexity**: O(1) - only storing two integer values, making it optimal for space efficiency

**Helper Structures:**
- No additional helper data structures are needed because we're solving this with a single pass through the array, maintaining only the necessary state at each step.

This minimal approach is optimal because we don't need to store any historical data or build complex structures - the problem's nature allows us to compute the answer incrementally with just two state variables.

## 5. Algorithm Walkthrough

Let me trace through the algorithm with a concrete example to demonstrate how it works:

**Example:** `prices = [7, 1, 5, 3, 6, 4]`

**Step-by-step execution:**

1. **Initialization**: `minPrice = Integer.MAX_VALUE`, `maxProfit = 0`

2. **i=0, price=7**: 
   - `minPrice = min(Integer.MAX_VALUE, 7) = 7`
   - `maxProfit = max(0, 7-7) = 0`

3. **i=1, price=1**:
   - `minPrice = min(7, 1) = 1`
   - `maxProfit = max(0, 1-1) = 0`

4. **i=2, price=5**:
   - `minPrice = min(1, 5) = 1`
   - `maxProfit = max(0, 5-1) = 4`

5. **i=3, price=3**:
   - `minPrice = min(1, 3) = 1`
   - `maxProfit = max(4, 3-1) = 4`

6. **i=4, price=6**:
   - `minPrice = min(1, 6) = 1`
   - `maxProfit = max(4, 6-1) = 5`

7. **i=5, price=4**:
   - `minPrice = min(1, 4) = 1`
   - `maxProfit = max(5, 4-1) = 5`

**Final result**: `maxProfit = 5`

**Key observations:**
- At each step, we maintain the minimum price seen so far (best buying opportunity)
- We calculate profit if we sold at current price using that minimum
- The algorithm naturally handles the constraint that we must buy before we sell
- We never need to look ahead - just process sequentially

**Edge case handling:**
- If prices are strictly decreasing, `maxProfit` remains 0 (no profit possible)
- If array has less than 2 elements, we return 0 (no transaction possible)
- The algorithm correctly handles duplicate prices by always taking the earliest minimum

The algorithm terminates because we process each element exactly once, and the invariants ensure optimal tracking of best buy/sell combination.

## 6. Java Solution

```java
public class BestTimeToBuyAndSellStock {
    /**
     * Finds the maximum profit from buying and selling stock once.
     * Uses a single pass approach maintaining minimum price seen so far
     * and tracking the maximum profit possible at each step.
     * 
     * @param prices Array of stock prices where prices[i] is the price on day i
     * @return Maximum profit achievable with one buy-sell transaction
     */
    public int maxProfit(int[] prices) {
        // Handle edge case of insufficient data
        if (prices == null || prices.length < 2) {
            return 0;
        }
        
        int minPrice = prices[0];  // Track the lowest price seen so far
        int maxProfit = 0;         // Track the maximum profit achievable
        
        // Start from day 1 since we need at least one previous day to buy
        for (int i = 1; i < prices.length; i++) {
            // If current price is lower than our minimum, update minPrice
            if (prices[i] < minPrice) {
                minPrice = prices[i];
            }
            // Otherwise calculate profit and update maxProfit if better
            else {
                int currentProfit = prices[i] - minPrice;
                maxProfit = Math.max(maxProfit, currentProfit);
            }
        }
        
        return maxProfit;
    }
}

7. Complexity Analysis

Time Complexity: O(n)

The algorithm makes a single pass through the input array of stock prices, visiting each element exactly once. Within each iteration, all operations (computation of minPrice, maxProfit, and updates) are O(1). Since we perform a constant amount of work for each of the n elements, the overall time complexity is O(n).

Space Complexity: O(1)

The solution uses only a constant amount of extra space regardless of input size:

• Two integer variables: minPrice and maxProfit
• One integer loop variable: i

No additional data structures are created that scale with input size. The space usage remains constant at O(1) throughout the execution.

Why These Bounds Are Correct

The time complexity is optimal for this problem because we must examine each price at least once to determine the best buy-sell combination. Any algorithm that solves this problem must process all n elements at least once, making O(n) the theoretical lower bound.

The space complexity is optimal because we only need to track the minimum price seen so far and the maximum profit achievable. These are scalar values that don't grow with input size, making O(1) the best possible space complexity for this problem.

The solution is optimal and near-optimal in both time and space dimensions, achieving the best possible performance characteristics for this canonical DSA problem.

8. Edge Cases & Pitfalls

Empty and Minimal Inputs

• Empty array: Handle gracefully with appropriate return value (typically 0 profit)
• Single element: No transaction possible, return 0
• Two elements: Only one valid transaction, return max(0, profit from single buy-sell)

Duplicate Values and Repeated States

• Identical prices: Multiple consecutive days with same price don't affect optimal solution
• Plateau regions: When prices stay constant, we should still track the minimum price seen so far
• Multiple local minima: Must correctly identify global minimum for optimal buy point

Boundary Conditions

• All decreasing prices: Should return 0 (no profit possible)
• All increasing prices: Should return difference between last and first price
• Large integer values: Need to handle potential overflow in profit calculation (though constraints typically prevent this)

Common Implementation Mistakes

• Incorrect initialization: Using first price as minPrice instead of initializing to max value or handling first element specially
• Off-by-one errors: Processing the same day twice for buy and sell operations
• Not updating minPrice properly: Only updating when a new minimum is found, not every iteration
• Ignoring edge case of no profit: Returning negative values instead of zero when no profitable transaction exists
• Using wrong variable names: Confusing minPrice with maxProfit or current price

// Example of problematic code:
// int minPrice = prices[0]; // This assumes we can buy on day 0
// But if prices are [5,4,3,2,1], we should return 0, not -1

The key is to always ensure that we're tracking the minimum price seen so far and only calculate profit when we have a valid buy-sell pair, with proper handling of the case where no positive profit is possible.

9. Alternative Approaches

There are several alternative approaches to solving the Best Time to Buy and Sell Stock problem, each with different trade-offs:

Brute Force Approach: Check all possible buy-sell pairs by examining every combination of indices where i < j. For each pair, calculate profit = prices[j] - prices[i]. This approach has O(n²) time complexity and O(1) space complexity. While simple to understand, it's inefficient for large inputs and doesn't leverage the key insight that we only need to track the minimum price seen so far.

Dynamic Programming with State Tracking: We can maintain two states at each day: the maximum profit if we hold a stock (maxProfitIfHolding) and the maximum profit if we don't hold a stock (maxProfitIfNotHolding). This approach uses O(1) space and O(n) time but requires more complex state management than the single-pass optimal solution.

Divide and Conquer: Split the array into halves recursively, compute the maximum profit in each half, and also compute the maximum profit crossing the boundary. This approach has O(n log n) time complexity due to the recursive structure, making it less efficient than our optimal O(n) solution.

Sliding Window with Two Pointers: Use two pointers to maintain a window where we track the minimum price and maximum profit. This is conceptually similar to our optimal approach but requires more careful handling of pointer movements and edge conditions.

The chosen single-pass optimal solution is preferred because it's the most efficient with O(n) time and O(1) space complexity, maintains clean logic flow, and is easy to understand and verify correctness. The alternatives either have worse time complexity or introduce unnecessary complexity without significant benefits for this specific problem.

10. Test Cases

public class BestTimeToBuyAndSellStock {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length < 2) {
            return 0;
        }
        
        int minPrice = Integer.MAX_VALUE;
        int maxProfit = 0;
        
        for (int price : prices) {
            minPrice = Math.min(minPrice, price);
            maxProfit = Math.max(maxProfit, price - minPrice);
        }
        
        return maxProfit;
    }
}

Sample test cases:

1. Normal case: [7, 1, 5, 3, 6, 4] → Expected: 5 (buy at 1, sell at 6)
2. Decreasing prices: [7, 6, 4, 3, 1] → Expected: 0 (no profit possible)
3. Increasing prices: [1, 2, 3, 4, 5] → Expected: 4 (buy at 1, sell at 5)
4. Single price: [5] → Expected: 0 (no transaction possible)
5. Empty array: [] → Expected: 0 (no transaction possible)
6. Duplicate prices: [2, 4, 1, 7, 1, 9] → Expected: 8 (buy at 1, sell at 9)
7. Two prices: [3, 7] → Expected: 4 (buy at 3, sell at 7)
8. Same prices: [5, 5, 5, 5] → Expected: 0 (no profit possible)
9. Large numbers: [1000000, 2000000, 3000000] → Expected: 2000000 (buy at 1000000, sell at 3000000)

The test cases cover normal scenarios, edge cases with minimal inputs, boundary conditions with duplicates, and performance considerations with large numbers. The solution handles all these cases correctly by maintaining the minimum price seen so far and computing maximum profit at each step.

11. Final Summary

The core idea is to track the minimum price seen so far while iterating through prices, calculating maximum profit at each step. This works because we can only sell after buying, so we're effectively looking for the best "buy low, sell high" opportunity. The solution is optimal with O(n) time and O(1) space, making a single pass through the array sufficient to find the maximum profit. The key insight is that we don't need to check all possible buy-sell pairs, but rather maintain the running minimum price and compute profit for each day's price against that minimum.