Best Time to Buy and Sell Stock Algorithm Solution

The best time to buy and sell stock problem presents a classic optimization challenge where we must determine the maximum profit achievable from a single buy-sell transaction. This solution explores multiple approaches including brute force, optimized single-pass, and dynamic programming techniques while analyzing their trade-offs in terms of time complexity, space efficiency, and practical applicability to real-world trading scenarios.

1. Problem Restatement

Clarifying questions to ask the interviewer:

1. Can the input array be empty or contain only one element? How should I handle those cases?
2. Are duplicate prices allowed in the input array? How should I treat identical consecutive prices?
3. Should I return the maximum profit value or also the indices of buy/sell days?
4. Can I mutate the input array, or do I need to preserve it?
5. What's the expected time complexity for the follow-up — O(n) or better?

Restated problem: Given an array of stock prices where each element represents the price on a specific day, find the maximum profit achievable by buying and selling one stock. You must buy before you sell, and you can only make one transaction.

Input/Output specification:

• Input: Integer array prices where prices[i] is the price on day i
• Output: Integer representing maximum profit possible (0 if no profit is achievable)
• Constraints:
  • Array length can be up to 10⁵ elements
  • Prices are positive integers (at least 1)
  • Must buy before sell (i.e., buyIndex < sellIndex)

Assumptions made:

• Prices are given in chronological order (index 0 = day 1, etc.)
• We can only make one buy-sell transaction (no multiple trades)
• Profit is calculated as sellPrice - buyPrice (not accounting for transaction fees)

Data shape and hidden structure: The input is a 1D array of integers with temporal ordering. The key insight is that we're looking for the maximum difference between any two elements where the smaller element comes before the larger one. This suggests we need to track minimum prices seen so far while iterating forward, which creates a natural optimization opportunity through single-pass scanning.

The problem has a hidden structure where we're essentially finding the maximum "price gap" in a sequence, but with the constraint that the smaller value must precede the larger one in time.

2. Pattern Recognition

Identified Patterns

The most likely pattern is "Single Pass with State Tracking" or "Sliding Window Maximum" variant.

Pattern Signals in Problem Wording

• "Best time to buy and sell stock" - suggests we're looking for optimal timing points
• "Only one transaction allowed" - indicates we need to find the best pair of indices where buy_index < sell_index
• "Maximize profit" - classic optimization problem with a clear objective function

Why This Fits the Pattern

This is fundamentally about finding the maximum difference between two elements in an array where the smaller element comes before the larger one. The key insight is that we're looking for a maximum subarray difference problem where:

• We want to maximize (sell_price - buy_price)
• With the constraint that buy_index < sell_index
• This is a classic "buy low, sell high" pattern

Core Insight

The core insight is that we don't need to check all pairs (which would be O(n²)). Instead, we can maintain the minimum price seen so far as we iterate through the array. For each day, if we sell that day, the best profit is achieved by buying at the lowest price seen so far.

This transforms the problem from a brute force O(n²) approach to an elegant O(n) linear scan solution where we track the running minimum and maximum profit simultaneously.

3. Approach Evolution

My first instinct is to consider a brute force approach where I check every possible buy-sell pair, but that's O(n²) because for each day I'd need to check all subsequent days to find the maximum profit. Let me think about how to optimize this.

I notice that if I maintain the minimum price seen so far as I iterate through the array, I can calculate the maximum profit at each step. This is a classic single-pass optimization pattern where we're looking for the best "difference" between two values in order.

The key insight is that at any given day, if I know the minimum price up to that point, then the maximum profit achievable by selling on that day is simply (current_price - min_price_so_far). This transforms the problem from checking all pairs to just tracking one running minimum.

Let me trace through this approach:

1. Keep track of the minimum price seen so far (best buying opportunity)
2. For each day, calculate profit if I sold today (current_price - min_price_so_far)
3. Keep track of the maximum profit seen so far
4. Update minimum price as I go

This is O(n) time and O(1) space, which is optimal for this problem since we must examine each price at least once.

The invariant I'm maintaining is: at any point in the iteration, minPrice represents the lowest price we've seen so far in the array, and maxProfit represents the maximum profit achievable by selling on any day up to the current day.

This approach is better than brute force because it eliminates redundant calculations and uses the fact that we can only sell after buying, which naturally enforces the chronological constraint.

4. Data Structure Choice

For this problem, I'll use a simple integer variable to track the minimum price seen so far and another to track the maximum profit.

Primary data structures:

• int minPrice - tracks the lowest price encountered so far as we iterate through the array
• int maxProfit - tracks the maximum profit achievable at each step

Why these are needed: The problem requires us to find the maximum difference between a selling price and a buying price where the buy happens before the sell. We need to maintain:

1. The minimum price seen so far (to know the best buying opportunity)
2. The maximum profit achievable at each point (to track our best selling decision)

Time and space impact:

• Time complexity: O(n) - we iterate once through the array
• Space complexity: O(1) - only using two integer variables regardless of input size

Helper structures: No additional helper data structures are needed. The solution can be implemented with just two variables that get updated in each iteration.

This approach is optimal because we're solving the problem with minimal memory overhead while maintaining linear time complexity. The simplicity of these two variables makes the code clean and easy to reason about, which is important in an interview setting where clarity matters as much as correctness.

The key insight is that we don't need to store all previous prices or use complex data structures - we only need to keep track of the running minimum and maximum difference, which can be captured with just two scalar variables.

5. Algorithm Walkthrough

Let me trace through the algorithm with a concrete example to demonstrate how it works step-by-step.

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

Step-by-step execution:

1. Initialization:

   • minPrice = Integer.MAX_VALUE (no price seen yet)
   • maxProfit = 0

2. Processing index 0 (price = 7):

   • minPrice = min(Integer.MAX_VALUE, 7) = 7
   • maxProfit = max(0, 7 - 7) = 0
   • State: minPrice = 7, maxProfit = 0

3. Processing index 1 (price = 1):

   • minPrice = min(7, 1) = 1
   • maxProfit = max(0, 1 - 1) = 0
   • State: minPrice = 1, maxProfit = 0

4. Processing index 2 (price = 5):

   • minPrice = min(1, 5) = 1
   • maxProfit = max(0, 5 - 1) = 4
   • State: minPrice = 1, maxProfit = 4

5. Processing index 3 (price = 3):

   • minPrice = min(1, 3) = 1
   • maxProfit = max(4, 3 - 1) = 4
   • State: minPrice = 1, maxProfit = 4

6. Processing index 4 (price = 6):

   • minPrice = min(1, 6) = 1
   • maxProfit = max(4, 6 - 1) = 5
   • State: minPrice = 1, maxProfit = 5

7. Processing index 5 (price = 4):

   • minPrice = min(1, 4) = 1
   • maxProfit = max(5, 4 - 1) = 5
   • State: minPrice = 1, maxProfit = 5

Final result: maxProfit = 5 (buy at price 1, sell at price 6)

Key observations:

• The algorithm maintains the invariant that minPrice always represents the lowest price seen so far
• At each step, we calculate what profit would be made if we sold today at the current price
• The maximum profit is tracked throughout the iteration
• Edge cases like decreasing prices are handled naturally - if no profitable transaction exists, maxProfit remains 0

The algorithm terminates correctly because we process all prices exactly once and maintain the necessary invariants throughout.

6. Java Solution

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 null or insufficient prices
        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 possible
        
        // 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 if we sell today and update maxProfit
            else {
                maxProfit = Math.max(maxProfit, prices[i] - minPrice);
            }
        }
        
        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, we perform constant-time operations: comparing the current price with the minimum price seen so far, and updating the maximum profit if a better opportunity is found. Since there are n elements in the input array and each operation takes O(1) time, the overall time complexity is O(n).

Space Complexity: O(1)

The solution uses only a constant amount of extra space regardless of the input size. We maintain just four integer variables: minPrice, maxProfit, currentPrice, and the loop index i. These variables do not scale with input size, so the space complexity is O(1).

Why these bounds are correct:

The time bound is tight because we must examine each price at least once to determine the optimal buy-sell pair. There's no way to know if a better profit exists without considering all prices in order. The space bound is optimal because we only need to track the essential state information (minimum price so far, maximum profit achievable) without storing any intermediate results or creating additional data structures that grow with input size.

This solution is optimal for the problem as stated, since we must read all input elements at least once to make any meaningful decision about buying and selling. Any algorithm solving this problem must have at least O(n) time complexity, making our solution asymptotically optimal.

8. Edge Cases & Pitfalls

Empty and Minimal Inputs

• Empty array: Handle gracefully with proper bounds checking to avoid ArrayIndexOutOfBoundsException
• Single element: No transaction possible, return 0 profit
• Two elements: Only one valid transaction, so we can compute directly

Duplicate Values and Repeated States

• Identical prices: Multiple consecutive days with same price don't change the optimal solution
• Plateau regions: When prices are flat, we should still track the minimum price seen so far for future transactions

Boundary Conditions

• All decreasing prices: Should return 0 (no profit possible)
• All increasing prices: Should return difference between last and first price
• Same min/max at different positions: Need to ensure we don't buy at the same time we sell

Common Implementation Mistakes

• Incorrect initialization: Using Integer.MAX_VALUE instead of prices[0] for min price when array has elements
• Off-by-one errors: Not properly handling the case where we buy on day 0 and sell on day 1
• State management: Not maintaining the invariant that we never buy at a price higher than our current minimum
• Index bounds: Accessing prices[i+1] without checking if i < prices.length - 1

// Example of incorrect initialization:
// int minPrice = Integer.MAX_VALUE; // Wrong - should be prices[0] when array is not empty
// int maxProfit = 0;

// Correct approach:
// if (prices.length <= 1) return 0;
// int minPrice = prices[0];
// int maxProfit = 0;

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 i < j and computing profit = prices[j] - prices[i]. This is O(n²) time complexity but O(1) space. While correct, it's inefficient for large inputs and doesn't leverage the sequential nature of the problem.

Dynamic Programming with State Machine: Model this as a state machine with states "hold" (owning stock) and "sold" (not owning stock). For each day, track the maximum profit when holding or not holding stock. This approach is O(n) time and O(1) space but requires more complex state management.

Divide and Conquer: Split the array into halves, compute maximum profit in each half, and find the maximum profit crossing the boundary (buying in left half, selling in right half). This approach is O(n log n) time and O(log n) space due to recursion stack, which is less efficient than the linear solution.

Two Pointers with Sliding Window: Use two pointers to maintain a window where we track minimum price so far and maximum profit. This is essentially the same as our optimal solution but framed differently - it's still O(n) time and O(1) space.

The chosen solution is preferred because it's the most intuitive, readable, and efficient approach that directly maps to the problem's core insight: we want to find the maximum difference between a later price and an earlier price, where the earlier price is minimized. The linear scan approach is optimal in both time and space complexity while remaining simple to understand and implement.

The alternative approaches either have worse time complexity or introduce unnecessary complexity for this specific problem structure.

10. Test Cases

public class BestTimeToBuyAndSellStock {
    
    public static void main(String[] args) {
        // Test case 1: Basic increasing prices
        int[] prices1 = {1, 2, 3, 4, 5};
        System.out.println("Test 1 - Expected: 4, Actual: " + maxProfit(prices1));
        
        // Test case 2: Basic decreasing prices
        int[] prices2 = {5, 4, 3, 2, 1};
        System.out.println("Test 2 - Expected: 0, Actual: " + maxProfit(prices2));
        
        // Test case 3: Mixed prices with profit
        int[] prices3 = {7, 1, 5, 3, 6, 4};
        System.out.println("Test 3 - Expected: 5, Actual: " + maxProfit(prices3));
        
        // Test case 4: Single price
        int[] prices4 = {5};
        System.out.println("Test 4 - Expected: 0, Actual: " + maxProfit(prices4));
        
        // Test case 5: Empty array
        int[] prices5 = {};
        System.out.println("Test 5 - Expected: 0, Actual: " + maxProfit(prices5));
        
        // Test case 6: All same prices
        int[] prices6 = {5, 5, 5, 5};
        System.out.println("Test 6 - Expected: 0, Actual: " + maxProfit(prices6));
        
        // Test case 7: Two elements with profit
        int[] prices7 = {2, 4};
        System.out.println("Test 7 - Expected: 2, Actual: " + maxProfit(prices7));
        
        // Test case 8: Two elements without profit
        int[] prices8 = {4, 2};
        System.out.println("Test 8 - Expected: 0, Actual: " + maxProfit(prices8));
        
        // Test case 9: Large numbers
        int[] prices9 = {1000000, 1000001, 1000002};
        System.out.println("Test 9 - Expected: 2, Actual: " + maxProfit(prices9));
        
        // Test case 10: Peak at beginning, valley at end
        int[] prices10 = {5, 1, 2, 3, 4};
        System.out.println("Test 10 - Expected: 3, Actual: " + maxProfit(prices10));
    }
    
    public static int maxProfit(int[] prices) {
        if (prices == null || prices.length <= 1) {
            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;
    }
}

The test cases cover:

1. Basic increasing prices - Validates the algorithm handles ascending sequences correctly
2. Basic decreasing prices - Confirms zero profit is returned when no gain possible
3. Mixed prices with optimal profit - Tests the core algorithm logic with real scenario
4. Single price - Edge case handling for minimal input size
5. Empty array - Validates null/empty input handling
6. All same prices - Tests duplicate values scenario
7. Two elements with profit - Simple case validation
8. Two elements without profit - Confirms zero profit logic
9. Large numbers - Validates handling of large integer values
10. Peak at beginning, valley at end - Tests that we find the best buy-sell combination regardless of position

Each test case includes both expected and actual results to verify correctness. The test cases are designed to cover all major edge cases including boundary conditions, duplicate values, and various price patterns that could break a naive implementation.

11. Final Summary

The core insight is that we need to track the minimum price seen so far while iterating through prices, allowing us to compute the maximum profit at each step. This greedy approach works because we can only make one transaction (buy once, sell once), so we're looking for the best "buy-low-sell-high" opportunity. The solution is optimal with O(n) time and O(1) space complexity, making it efficient for large input sizes. The key is recognizing that we don't need to look ahead or maintain complex state—we just need to keep track of the running minimum and maximum profit as we scan through the array once.