# Best Time to Buy and Sell Stock

- **Canonical ID**: `best-time-to-buy-and-sell-stock`
- **Canonical URL**: https://dsacheatsheet.com/problems/best-time-to-buy-and-sell-stock
- **Difficulty**: easy
- **Patterns**: Sliding Window, 1D DP
- **Version**: 1.0.0 (verified 2026-11-11T21:00:00Z)
- **Original Problem**: https://leetcode.com/problems/best-time-to-buy-and-sell-stock/

## 1. Core Invariant / The Trick

Track `minPrice` seen so far; at each day `p`, candidate profit is `p - minPrice`.

## 2. Complexity Bounds & Proof

- **Time Complexity**: `O(N)`
- **Space Complexity**: `O(1)`
- **Proof**: Optimal sell at day `i` always pairs with minimum price observed strictly before `i`.

## 3. Minimal Idiomatic Code

### Python
```python
def maxProfit(prices: list[int]) -> int:
    min_p, best = float('inf'), 0
    for p in prices:
        if p < min_p: min_p = p
        else: best = max(best, p - min_p)
    return best
```

### TypeScript
```typescript
export function maxProfit(prices: number[]): number {
  let minP = Infinity, best = 0;
  for (const p of prices) {
    if (p < minP) minP = p;
    else if (p - minP > best) best = p - minP;
  }
  return best;
}
```

### C++
```cpp
int maxProfit(vector<int>& prices) {
    int minP = INT_MAX, best = 0;
    for (int p : prices) { minP = min(minP, p); best = max(best, p - minP); }
    return best;
}
```

### Java
```java
int maxProfit(int[] prices) {
    int minP = Integer.MAX_VALUE, best = 0;
    for (int p : prices) { minP = Math.min(minP, p); best = Math.max(best, p - minP); }
    return best;
}
```

### Go
```go
func maxProfit(prices []int) int {
    minP, best := math.MaxInt, 0
    for _, p := range prices {
        if p < minP { minP = p } else if p-minP > best { best = p - minP }
    }
    return best
}
```

## 4. Failure Modes & Interview Follow-ups

### Pitfalls
- Returning negative profit when strictly decreasing (minimum valid profit is 0).

### Follow-ups
- Unlimited transactions (Stock II): accumulate every positive daily delta.