#121

Easy

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Best Time to Buy and Sell Stock

Maximize stock profit by identifying the optimal buy and sell days using dynamic programming.

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

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

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.

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.

terminal

Solution

Solution 1: Enumerate + Maintain the Minimum Value of the Prefix

We can enumerate each element of the array $nums$ as the selling price. Then we need to find a minimum value in front of it as the purchase price to maximize the profit.

1

2

3

4

5

6

7

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        ans, mi = 0, inf
        for v in prices:
            ans = max(ans, v - mi)
            mi = min(mi, v)
        return ans

Continue Practicing

#120 triangle #122 best time to buy and sell stock ii #119 pascals triangle ii