How to Solve Best Time to Buy and Sell Stock

To solve the Best Time to Buy and Sell Stock problem, identify the best day to buy and the best day to sell using dynamic programming. The goal is to find the maximum possible profit by comparing stock prices, ensuring the buy day is before the sell day. Efficient algorithms can achieve this in linear time with constant space.

Problem Statement

You are given an array, prices, where prices[i] is the price of a stock on day i. Your task is to determine the best day to buy the stock and the best day to sell it in the future, aiming to maximize your profit.

Return the maximum profit you can achieve by making exactly one buy and one sell. If no profit can be made, return 0. Remember, you must buy before you sell, and the transaction must be valid within the array's given days.

Examples

Example 1

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

Output: 5

Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5. Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.

Example 2

Input: prices = [7,6,4,3,1]

Output: 0

In this case, no transactions are done and the max profit = 0.

Constraints

• 1 <= prices.length <= 105
• 0 <= prices[i] <= 104

Solution Approach

Brute Force Approach

In the brute force solution, iterate over all possible pairs of buy and sell days, calculating the profit for each pair. This results in an O(n^2) time complexity but guarantees correctness.

Optimized Approach Using Dynamic Programming

An optimized solution involves maintaining the minimum price encountered so far. For each day's price, compute the potential profit if selling on that day, updating the maximum profit accordingly. This reduces the time complexity to O(n).

Space Optimization

For the dynamic programming approach, maintain only the current minimum price and the current maximum profit, achieving O(1) space complexity. This is the most efficient space-wise solution while maintaining the O(n) time complexity.

Complexity Analysis

The brute force approach has a time complexity of O(n^2) due to the double loop for all pairs of buy and sell days. The optimized dynamic programming approach reduces the time complexity to O(n) by iterating over the array once. Space complexity is O(1) in the optimized approach, as only a few variables are needed to track the minimum price and maximum profit.

What Interviewers Usually Probe

• Look for understanding of dynamic programming concepts, especially in handling state transitions.
• Evaluate the candidate’s ability to optimize space and time complexity effectively.
• Assess how well the candidate can explain trade-offs between brute force and optimized solutions.

Common Pitfalls or Variants

Common pitfalls

• Failing to account for the requirement that the buy day must be before the sell day.
• Overcomplicating the solution with unnecessary loops or operations when a single pass through the array suffices.
• Not considering edge cases such as when no profit can be made (e.g., prices are strictly decreasing).

Follow-up variants

• Modify the problem to allow multiple transactions (i.e., multiple buy-sell pairs).
• Change the problem to maximize profit over a certain number of transactions instead of just one.
• Introduce a constraint on transaction fees and calculate the profit after accounting for such fees.

How GhostInterview Helps

• GhostInterview walks you through the step-by-step approach for both brute force and dynamic programming techniques, ensuring you understand the correct patterns.
• The solver helps you optimize your solution for both time and space complexity, highlighting critical trade-offs.
• With practical problem breakdowns and real-time feedback, GhostInterview ensures you are interview-ready with efficient solutions.

Topic Pages

• Array
• Dynamic Programming

Related GhostInterview Pages

• LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
• Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
• How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.

FAQ

What is the optimal approach for solving the Best Time to Buy and Sell Stock problem?

The optimal approach uses dynamic programming, where you track the minimum price encountered so far and compute the maximum profit by comparing the current price with the minimum.

Can the Best Time to Buy and Sell Stock problem be solved using brute force?

Yes, it can be solved with a brute force approach by checking all possible pairs of buy and sell days, but this results in O(n^2) time complexity, which is inefficient.

What is the time complexity of the dynamic programming approach for Best Time to Buy and Sell Stock?

The time complexity of the dynamic programming approach is O(n), where n is the length of the prices array, as it requires only a single pass through the array.

How does GhostInterview help with the Best Time to Buy and Sell Stock problem?

GhostInterview offers an interactive solver that guides you through multiple approaches, helps you optimize your solution, and provides real-time feedback for improving your approach.

What should I consider when optimizing my solution for the Best Time to Buy and Sell Stock problem?

Consider optimizing both time and space complexity. The dynamic programming approach provides an O(n) solution with O(1) space, making it the most efficient for large inputs.