Best Time to Buy and Sell Stock

Difficulty: Easy
LeetCode Pattern: Arrays & Hashing

You are given an array prices where prices[i] is the stock price on i^th day.

Return the max profit you can make by buying on one day and selling on a later day.

Return 0 if no profit is possible.

Input: prices = [3,2,1]
Output: 0
Reason:
· Prices are only decreasing.
· So can't make any profit.
Input: prices = [2,1,5]
Output: 4
Reason:
· Buy at price = 1
· Sell at price = 5
· Profit = 5-1 = 4

• Can the input array be empty?

  • Yes.

  • Return 0 in that case.

• Will it be sorted?

  • No, not always.

• Could prices be negative?

  • Assume they won’t be.

1/ Nested Loop (Brute Force ⚠️)

• Logic:

  • For each price:

    • Try selling it on all future days

    • Keep track of the max profit

  • Return the max profit in the end

• Big O:

  • Time Complexity: O(n²)

  • Space Complexity: O(1)

2/ Track Min Price (Optimal ✅)

• Logic:

  • Keep track of min price at all times

  • For each price:

    • Update min price if needed

    • Update max profit if needed

  • Return the max profit in the end

• Big O:

  • Time Complexity: O(n)

  • Space Complexity: O(1)

• How to return the days (not prices)?

  • Track the min price day index

  • When updating max profit:

    • Store the min price day index

    • Store the current day index

  • Return both indices at the end

• What if multiple buys and sells were allowed?

  • No need to track min price

  • Keep track of total profit

  • Anytime the price increases:

    • add the difference to total profit

  • Return this total profit at the end