How to attack any problem

Blank screen? Run four steps before you write a single line: read the constraints, brute force first, then optimise, then test the edges. Worked example: LeetCode 121, Best Time to Buy and Sell Stock (Easy).

The idea

Nobody visits a friend by first hunting for the perfect shortcut. You check how long you have, take any route that works, then look for a shortcut, and finally check it is the right house.

Read the constraints. The problem page says 1 <= prices.length <= 10^5. A computer does about 100 million steps in a second. O(n²) on 100,000 prices is 10 billion steps, too slow, so aim for O(n).

Input size up to Aim for Why
1,000 O(n²) 1,000² is 1,000,000 steps. Fine.
100,000 O(n) 100,000² is 10 billion steps. Too slow.
1,000,000,000 O(log n) Even one pass is too many steps.
Brute force first. Try every buy day and every later sell day. Slow, but correct.
Then optimise. To sell on a given day you only need the cheapest price before it, so keep it in one variable.
Test the edges. [5], [7, 6, 4, 3, 1] and [2, 2, 2] all return 0.

Input size up to	Aim for	Why
1,000	O(n²)	1,000² is 1,000,000 steps. Fine.
100,000	O(n)	100,000² is 10 billion steps. Too slow.
1,000,000,000	O(log n)	Even one pass is too many steps.

The walk

prices = [7, 1, 5, 3, 6, 4] returns 5 (buy at 1, sell at 6).

price	7	1	5	3	6	4
cheapest	7	1	1	1	1	1
best	0	0	4	4	5	5

Pseudocode

The first function is the brute force from slide 4, the second is the one pass from slide 5.

Pseudocode · any language

function maxProfit(prices):
    n = length(prices)
    best = 0
    for buy from 0 to n - 1:
        for sell from buy + 1 to n - 1:
            profit = prices[sell] - prices[buy]
            best = max(best, profit)
    return best

function maxProfit(prices):
    cheapest = prices[0]
    best = 0
    for each price in prices:
        cheapest = min(cheapest, price)
        best = max(best, price - cheapest)
    return best

The trap: deleting the slow version once the fast one works. Keep it, and run both on many inputs. Different answers? The fast one has a bug.

Code

class Solution {
    // Brute force: O(n^2) time, O(1) space
    public int maxProfitBrute(int[] prices) {
        int n = prices.length;
        int best = 0;
        for (int buy = 0; buy < n; buy++) {
            for (int sell = buy + 1; sell < n; sell++) {
                int profit = prices[sell] - prices[buy];
                best = Math.max(best, profit);
            }
        }
        return best;
    }

    // One pass: O(n) time, O(1) space
    public int maxProfit(int[] prices) {
        int cheapest = prices[0];
        int best = 0;
        for (int price : prices) {
            cheapest = Math.min(cheapest, price);
            best = Math.max(best, price - cheapest);
        }
        return best;
    }
}

class Solution:
    # Brute force: O(n^2) time, O(1) space
    def maxProfitBrute(self, prices: list[int]) -> int:
        n = len(prices)
        best = 0
        for buy in range(n):
            for sell in range(buy + 1, n):
                profit = prices[sell] - prices[buy]
                best = max(best, profit)
        return best

    # One pass: O(n) time, O(1) space
    def maxProfit(self, prices: list[int]) -> int:
        cheapest = prices[0]
        best = 0
        for price in prices:
            cheapest = min(cheapest, price)
            best = max(best, price - cheapest)
        return best

class Solution {
public:
    // Brute force: O(n^2) time, O(1) space
    int maxProfitBrute(vector<int>& prices) {
        int n = prices.size();
        int best = 0;
        for (int buy = 0; buy < n; buy++) {
            for (int sell = buy + 1; sell < n; sell++) {
                int profit = prices[sell] - prices[buy];
                best = max(best, profit);
            }
        }
        return best;
    }

    // One pass: O(n) time, O(1) space
    int maxProfit(vector<int>& prices) {
        int cheapest = prices[0];
        int best = 0;
        for (int price : prices) {
            cheapest = min(cheapest, price);
            best = max(best, price - cheapest);
        }
        return best;
    }
};

// Brute force: O(n^2) time, O(1) space
function maxProfitBrute(prices) {
    const n = prices.length;
    let best = 0;
    for (let buy = 0; buy < n; buy++) {
        for (let sell = buy + 1; sell < n; sell++) {
            const profit = prices[sell] - prices[buy];
            best = Math.max(best, profit);
        }
    }
    return best;
}

// One pass: O(n) time, O(1) space
function maxProfit(prices) {
    let cheapest = prices[0];
    let best = 0;
    for (const price of prices) {
        cheapest = Math.min(cheapest, price);
        best = Math.max(best, price - cheapest);
    }
    return best;
}

Complexity

Version	Time	Extra space
Brute force	O(n²)	O(1)
One pass	O(n)	O(1)

How it was tested

All four languages return 5 on the example and 0 on each edge case. Both versions in all four languages were then run on 3,005 inputs (3,000 random price lists of length 1 to 12, the examples, and one list of 3,000 prices) and matched an independent brute force on every one.