17 · Best Time to Buy and Sell Stock

In an Xcode test target:

import Testing

struct BestTimeToBuyAndSellStockTests {

    @Test(arguments: [
        ([8, 3, 6, 2, 7, 4], 5),
        ([4, 10, 1, 5], 6),
        ([9, 7, 4, 1], 0),
    ])
    func returnsTheBiggestGainFromOneBuyThenOneLaterSell(prices: [Int], expected: Int) {
        #expect(maxProfit(prices) == expected)
    }

    // MARK: - Privates
    private func maxProfit(_ prices: [Int]) -> Int {
        0
    }
}

In a playground:

func maxProfit(_ prices: [Int]) -> Int {
    0 // your solution
}

let cases: [([Int], Int)] = [
    ([8, 3, 6, 2, 7, 4], 5),
    ([4, 10, 1, 5], 6),
    ([9, 7, 4, 1], 0),
]
for (prices, expected) in cases {
    let got = maxProfit(prices)
    print(got == expected ? "PASS" : "FAIL", prices, "→", got, "expected", expected)
}

Sliding window with a running minimum. The cue is "buy on one day, sell on a later day": a pair of positions where the left one must come first, scanned once from left to right. The left edge of the window sits on the cheapest day seen so far; the right edge is today. The left edge only ever jumps forward, to a new low.

Walk through the days once and remember two numbers: the cheapest price seen so far, and the best profit seen so far. On each day, first ask "is today the cheapest day yet?" and update the cheapest price if so. Then ask "if I sold today, having bought on the cheapest day before it, would that beat my best?" and update the best profit if so. At the end, the best profit is the answer.

That covers every useful plan: for any sell day, the best buy day is simply the cheapest day before it, and the running minimum is exactly that.

Time O(n): one look at each day. Space O(1): two numbers.

func maxProfit(_ prices: [Int]) -> Int {
    var cheapest = Int.max
    var best = 0

    for price in prices {
        cheapest = min(cheapest, price)          // best day to have bought, up to today
        best = max(best, price - cheapest)       // sell today against that day
    }
    return best
}

Updating cheapest before computing the profit means a same-day buy and sell is considered, which is worth 0 and so never wins — harmless, and it removes a special case. best starts at 0, so falling prices and an empty array both return 0.

Verified with swift test on Swift 6.4 in Swift 6 mode: the three examples above, five more (empty, one day, flat prices, a single 0-to-10,000 jump, and a zigzag), and 3,000 random arrays checked against a brute-force search over every buy and sell pair.

[4, 10, 1, 5]

Answer 6. This is the example that sinks "find the lowest price, then the highest price after it": the lowest price is 1, and the best you can do from there is 4.

[9, 7, 4, 1] — every day is a new low, so every "profit selling today" is 0 and best never moves off 0.

A one-liner that is secretly O(n²). Swift makes it tempting to write prices.indices.map { prices[$0] - (prices[...$0].min() ?? 0) }.max(). It reads like one pass and it compiles cleanly, but prices[...$0] is an ArraySlice and .min() walks the whole slice every time, so the work grows with the square of the length — the brute force with nicer spelling. Slicing is O(1); anything you call on the slice is not. The other half of the trap is prices.min() returning an Optional: starting from prices[0] or prices.first! crashes on an empty array, which is why the solution starts cheapest at Int.max. price - Int.max is negative, not an overflow, so it is safe here.

• "Return the two days, not the profit." → Keep the index of the cheapest day alongside its price, and record that index plus today's index whenever best improves.
• "You can trade as many times as you like, one share at a time." → Add up every rise from one day to the next: max(0, prices[i] − prices[i − 1]) summed. Greedy, O(n).
• "At most two trades." → Four running numbers — best after first buy, first sell, second buy, second sell — updated in that order each day. Still O(n), O(1); it's the step towards dynamic programming.