Arrays & Strings
How Arrays & Strings work
Why it matters
Price histories can contain years of ticks, so checking every possible buy and later sale quickly becomes too expensive. Trading dashboards still need the best gain for a chart as soon as its prices arrive. The solution must preserve the buy-before-sell rule while finding the largest profit without comparing every pair of days.
Example
Best Time to Buy and Sell Stock
prices[i] is the price of a stock on day i. You may buy once and sell once later. Return the maximum profit, or 0 if no profit is possible.
- Input
- prices = [7, 1, 5, 3, 6, 4]
- Output
- 5
Approach 1 · Brute force
Try every pair of days
Same example
prices = [7, 1, 5, 3, 6, 4]
Buy on one day, sell on any later day, and keep the largest difference. That checks every pair of days, n(n − 1)/2 pairs for n prices.
Time O(n²) · Space O(1)
Python
Best Time to Buy and Sell Stock
- 1def maxProfit(prices):
- 2 best = 0
- 3 for buy in range(len(prices)):buy = 0
- 4 for sell in range(buy + 1, len(prices)):sell = 1
- 5 best = max(best, prices[sell] - prices[buy])
- 6 return best
Buy at 7, sell at 1: profit -6. Best stays 0.
Approach 2 · Resolve the bottleneck
The idea
Keep one example in view
Best Time to Buy and Sell Stock
prices = [7, 1, 5, 3, 6, 4]→5
The baseline, Try every pair of days, is O(n²) · O(1). The better model below keeps this exact input and removes that bottleneck.
In [7, 1, 5, 3, 6, 4], selling at 6 pairs with the cheapest earlier price, 1, for profit 5. Instead of checking all 15 legal day pairs, carry the cheapest earlier price and best profit through one pass.
In prices = [7, 1, 5, 3, 6, 4], each price has an index, so reading prices[i] takes O(1). The cost comes from how often you walk those six slots: checking all buy-and-sell pairs nests one walk inside another.
Carry low and best through one walk. After 7, low is 7; at 1, low becomes 1. Prices 5, 3, 6, and 4 can each be tested as today's sale against that earlier 1. Selling at 6 raises best to 5, and the final 4 cannot beat it.
1000
nums[0]
1004
nums[1]
1008
nums[2]
1012
nums[3]
1016
nums[4]
address(i) = base + i × 4
nums[2] → 1000 + 2 × 4 = 1008
Run the same example
Walkthrough
- 1.Set low to the first price and best to 0.
- 2.At each price, if it is below low, it becomes the new low.
- 3.Otherwise, try selling today: best = max(best, price − low).
- 4.After the walk, best is the answer. If prices only fall, it stays 0.
Python
Best Time to Buy and Sell Stock
- Input:
- prices = [7, 1, 5, 3, 6, 4]
- Output:
- 5
- 1def maxProfit(prices):
- 2 low = prices[0]
- 3 best = 0
- 4 for price in prices:
- 5 if price < low:
- 6 low = price
- 7 best = max(best, price - low)
- 8 return best
Start with the first price as the lowest seen, and no profit yet.
Complexity
TimeO(n)
SpaceO(1)
One pass over n prices with constant work per price is O(n) time. You keep two numbers, low and best, so extra space is O(1). The brute force does the same subtraction for every pair of days, about n²/2 times.
Where this breaks
One remembered low only works when you buy and sell once. Several rises and falls need a new decision on each day.
Brute force
Every pair of days
O(n²) time
O(1) space
This technique
Track the lowest price
O(n) time
O(1) space
n=100
n=1,000
n=10,000
Price comparisons on a log scale. At 10,000 days the pair check does about 5,000 times more work.
Your turn
Best Time to Buy and Sell Stock
Same problem, your code.
Solve Best Time to Buy and Sell StockThen branch out
Same technique, different problems. Try them without the walkthrough.