Best Time to Buy and Sell Stock

Difficulty: Easy | Acceptance: 56.70% | Paid: No Topics: Array, Dynamic Programming

You are given an array prices where prices[i] is the price of a given stock on the ith day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

• Examples
• Constraints
• Brute Force
• One Pass
• Kadane’s Algorithm

Examples

Example 1:

Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: 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
Explanation: In this case, no transactions are done and the max profit = 0.

Constraints

- 1 <= prices.length <= 10^5
- 0 <= prices[i] <= 10^4

Brute Force

Intuition The most straightforward way to solve this problem is to consider every possible pair of days where the buy day comes before the sell day. We calculate the profit for each pair and keep track of the maximum profit found.

Steps

• Initialize a variable max_profit to 0.
• Use a nested loop: the outer loop iterates from the first day to the second-to-last day (i), and the inner loop iterates from the current day i to the last day (j).
• For each pair (i, j), calculate the profit as prices[j] - prices[i].
• If this profit is greater than max_profit, update max_profit.
• After checking all pairs, return max_profit.

class Solution:
    def maxProfit(self, prices: list[int]) -> int:
        max_profit = 0
        n = len(prices)
        for i in range(n - 1):
            for j in range(i + 1, n):
                profit = prices[j] - prices[i]
                if profit > max_profit:
                    max_profit = profit
        return max_profit

Complexity

• Time: O(n²) - We use two nested loops to check every pair.
• Space: O(1) - We only use a few variables for storage.
• Notes: This approach is simple but inefficient for large inputs, leading to Time Limit Exceeded (TLE) errors.

One Pass

Intuition We can optimize the solution by iterating through the array only once. We keep track of the minimum price encountered so far. For each subsequent price, we calculate the potential profit if we sold at that price (current price - minimum price) and update the maximum profit if this potential profit is higher.

Steps

• Initialize min_price to a very large number (e.g., infinity) and max_profit to 0.
• Iterate through the prices array.
• If the current price is less than min_price, update min_price to the current price.
• Otherwise, calculate the profit (current price - min_price). If this profit is greater than max_profit, update max_profit.
• After the loop finishes, return max_profit.

class Solution:
    def maxProfit(self, prices: list[int]) -> int:
        min_price = float('inf')
        max_profit = 0
        for price in prices:
            if price < min_price:
                min_price = price
            elif price - min_price > max_profit:
                max_profit = price - min_price
        return max_profit

Complexity

• Time: O(n) - We traverse the list only once.
• Space: O(1) - We only use two variables regardless of the input size.
• Notes: This is the optimal solution for this problem.

Kanee’s Algorithm

Intuition This problem can be reduced to finding the maximum subarray sum. If we calculate the difference between consecutive days (prices[i] - prices[i-1]), we get an array of daily price changes. The maximum profit is simply the maximum sum of a contiguous subarray within this difference array.

Steps

• Initialize two variables: current_sum to 0 and max_sum to 0.
• Iterate through the prices array starting from the second element (index 1).
• Calculate the difference between the current price and the previous price.
• Add this difference to current_sum.
• If current_sum becomes negative, reset it to 0 (as a negative sum would decrease any future profit).
• If current_sum is greater than max_sum, update max_sum.
• Return max_sum.

class Solution:
    def maxProfit(self, prices: list[int]) -> int:
        max_sum = 0
        current_sum = 0
        for i in range(1, len(prices)):
            current_sum += prices[i] - prices[i-1]
            if current_sum < 0:
                current_sum = 0
            if current_sum > max_sum:
                max_sum = current_sum
        return max_sum

Complexity

• Time: O(n) - We iterate through the array once.
• Space: O(1) - We only use two variables.
• Notes: This approach is mathematically equivalent to the One Pass approach but framed in terms of maximum subarray sum.