# Best Time to Buy and Sell Stock with Cooldown

- **Canonical ID**: `best-time-to-buy-and-sell-stock-with-cooldown`
- **Canonical URL**: https://dsacheatsheet.com/problems/best-time-to-buy-and-sell-stock-with-cooldown
- **Difficulty**: medium
- **Patterns**: 2D DP
- **Version**: 1.0.0 (verified 2026-11-11T21:20:00Z)
- **Original Problem**: https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/

## 1. Core Invariant / The Trick

Three-state machine on day `i`: `hold` (currently holding share), `sold` (just sold today -> enters cooldown tomorrow), `rest` (not holding, cooled off). Transitions: `hold = max(hold, rest - p)`, `rest = max(rest, sold)`, `sold = prev_hold + p`.

## 2. Complexity Bounds & Proof

- **Time Complexity**: `O(N)`
- **Space Complexity**: `O(1)`
- **Proof**: State-machine FSM reduces 2D `(day, state)` DP table into 3 rolling integer registers.

## 3. Minimal Idiomatic Code

### Python
```python
def maxProfit(prices: list[int]) -> int:
    hold, sold, rest = float('-inf'), 0, 0
    for p in prices:
        prev_hold = hold
        hold = max(hold, rest - p)
        rest = max(rest, sold)
        sold = prev_hold + p
    return max(sold, rest)
```

### TypeScript
```typescript
export function maxProfit(prices: number[]): number {
  let hold = -Infinity, sold = 0, rest = 0;
  for (const p of prices) {
    const prevHold = hold;
    hold = Math.max(hold, rest - p);
    rest = Math.max(rest, sold);
    sold = prevHold + p;
  }
  return Math.max(sold, rest);
}
```

### C++
```cpp
int maxProfit(vector<int>& prices) {
    int hold = INT_MIN / 2, sold = 0, rest = 0;
    for (int p : prices) {
        int ph = hold;
        hold = max(hold, rest - p);
        rest = max(rest, sold);
        sold = ph + p;
    }
    return max(sold, rest);
}
```

### Java
```java
int maxProfit(int[] prices) {
    int hold = Integer.MIN_VALUE / 2, sold = 0, rest = 0;
    for (int p : prices) {
        int ph = hold;
        hold = Math.max(hold, rest - p);
        rest = Math.max(rest, sold);
        sold = ph + p;
    }
    return Math.max(sold, rest);
}
```

### Go
```go
func maxProfit(prices []int) int {
    hold, sold, rest := math.MinInt/2, 0, 0
    for _, p := range prices {
        ph := hold
        hold = max(hold, rest-p)
        rest = max(rest, sold)
        sold = ph + p
    }
    return max(sold, rest)
}
```

## 4. Failure Modes & Interview Follow-ups

### Pitfalls
- Allowing `rest - p` to transition directly from `sold` skips the mandatory 1-day cooldown.
- Initialize `hold = -inf, sold = 0, rest = 0` so selling before buying is impossible.

### Follow-ups
- Stock with Transaction Fee drops `sold` state and subtracts `fee` on sell; Stock IV limits to `k` transactions (`O(N * k)` states).