How do you solve Best Time to Buy and Sell Stock on LeetCode?

Best Time to Buy and Sell Stock (LeetCode #121) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(1) space complexity. Key insight: The key to maximizing profit is to always buy at the lowest price before selling.

What is the brute force solution for Best Time to Buy and Sell Stock?

The brute force approach for Best Time to Buy and Sell Stock is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach checks every possible pair of buy and sell days to find the maximum profit. This is straightforward but inefficient for large inputs. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Best Time to Buy and Sell Stock?

Best Time to Buy and Sell Stock uses the following concepts: Array, Dynamic Programming. The recommended patterns to study are: Array, Dynamic Programming.

What are the interview tips for Best Time to Buy and Sell Stock?

Always clarify the constraints and edge cases before diving into coding. Think about how you can reduce the problem size — in this case, using a single pass. Practice explaining your thought process as you code; it helps solidify your understanding.

What are common mistakes when solving Best Time to Buy and Sell Stock?

Students often forget to ensure that the buy day comes before the sell day. Some may try to calculate profits in a nested loop without realizing a single pass is sufficient.

#121

Best Time to Buy and Sell Stock

Easy

ArrayDynamic ProgrammingArrayDynamic Programming

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(1)

💡

Intuition

Time O(n)Space O(1)

The optimal solution tracks the minimum price seen so far while iterating through the prices. This allows us to calculate the potential profit in constant time, leading to a much more efficient solution.

⚙️

Algorithm

5 steps

1Step 1: Initialize min_price to infinity and max_profit to 0.
2Step 2: Loop through each price in the prices array.
3Step 3: For each price, update min_price if the current price is lower than min_price.
4Step 4: Calculate the profit as current price - min_price. If this profit is greater than max_profit, update max_profit.
5Step 5: After the loop, return max_profit.

solution.py13 lines

1# Full working Python code
2prices = [7,1,5,3,6,4]
3def maxProfit(prices):
4    min_price = float('inf')
5    max_profit = 0
6    for price in prices:
7        if price < min_price:
8            min_price = price
9        profit = price - min_price
10        if profit > max_profit:
11            max_profit = profit
12    return max_profit
13print(maxProfit(prices))

ℹ

Complexity note: This complexity is achieved because we only make a single pass through the prices array, updating our min_price and max_profit in constant time.

1The key to maximizing profit is to always buy at the lowest price before selling.
2You only need to keep track of the minimum price seen so far to calculate potential profits efficiently.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.