Problem

We are given an array prices, where prices[i] represents the price of a stock on the ith day.

The goal is to choose one day to buy the stock and a later day to sell it, maximizing the profit.

If no profit can be made, we return 0.

Brute Force Approach

The simplest idea is to try every possible pair of buy and sell days.

from typing import List

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        profit = 0

        for i in range(len(prices)):
            for j in range(i + 1, len(prices)):
                profit = max(profit, prices[j] - prices[i])

        return profit

For every day i, we treat it as the buying day. Then we check every future day j as the selling day.

This works, but it is too slow for large inputs.

Time complexity: O(n²)
Space complexity: O(1)

Two Pointer Approach

We can improve the solution using two pointers.

The left pointer l represents the buying day, and the right pointer r represents the selling day.

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        profit = 0
        l, r = 0, 1

        while r < len(prices):
            if prices[r] > prices[l]:
                profit = max(profit, prices[r] - prices[l])
            else:
                l = r

            r += 1

        return profit

If the price at r is greater than the price at l, we calculate the profit.

If the price at r is smaller, then it is better to buy at r, so we move l to r.

Time complexity: O(n)
Space complexity: O(1)

One Pass Minimum Price Approach

Another clean way to solve the problem is to keep track of the lowest price seen so far.

For each price, we calculate the profit we would get if we sold on that day.

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        minPrice = prices[0]
        maxP = 0

        for price in prices:
            profit = price - minPrice
            maxP = max(maxP, profit)
            minPrice = min(minPrice, price)

        return maxP

Here, minPrice stores the best buying price so far.

For every price, we check:

profit = price - minPrice

Then we update the maximum profit.

Finally, we update minPrice if we find a smaller price.

Time complexity: O(n)
Space complexity: O(1)

Example Walkthrough

For:

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

The best day to buy is when the price is 1.

The best day to sell after that is when the price is 6.

So the maximum profit is:

6 - 1 = 5

Output:

5

Key Idea

The important rule is that we must buy before we sell.

So while scanning the array, we keep track of the cheapest price seen so far and calculate the best possible profit at each step.

This avoids checking every pair and gives us an efficient one-pass solution.

Final Solution

from typing import List

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        minPrice = prices[0]
        maxP = 0

        for price in prices:
            profit = price - minPrice
            maxP = max(maxP, profit)
            minPrice = min(minPrice, price)

        return maxP

This is the most optimal solution because it only scans the array once.