Maximum Drawdown in a Sliding Window
Given an array of prices prices of length $n$ and a window size $k$, compute the maximum drawdown within each sliding window of size $k$.
Implement the function with signature:
```python def max_drawdown(prices, k): ```
It must return a list of length $n - k + 1$, where the entry for each window is the largest peak-to-trough decline: $\max_{i \le j}(\text{prices}[i] - \text{prices}[j])$ where $i$ and $j$ are indices within the window and $i \le j$ (the peak must come before the trough). If a window is non-decreasing the drawdown is $0$.
Constraints: - $1 \le k \le n \le 10^5$ - $0 \le \text{prices}[i] \le 10^6$
Example
max_drawdown([10, 8, 12, 7, 11, 9, 6], 4) -> [5, 5, 5, 5]
The windows are [10,8,12,7], [8,12,7,11], [12,7,11,9], [7,11,9,6]. In the first three the peak 12 precedes the trough 7, giving 12 - 7 = 5; in the last, peak 11 precedes trough 6, giving 11 - 6 = 5.
Hints
- Start with the brute force: for each window, scan left to right tracking the running peak and the largest drop from that peak.
- To improve beyond $O(nk)$, you need a data structure that supports range queries. But drawdown is not simply max minus min -- the max must come before the min.
- Define a segment tree node as (max_drawdown, prefix_max, suffix_min). When merging two adjacent intervals, the cross-interval drawdown is left's prefix_max minus right's suffix_min.
Worked Solution
How to Think About It: This is a harder variant of the sliding window maximum problem (LeetCode 239). The twist is that drawdown is not just a single extremum -- it is the difference between a running prefix-max and the current price, with the constraint that the peak must come before the trough. The brute force $O(nk)$ approach scans each window left to right, tracking a running peak, and records the largest drop from that peak.
Algorithm:
*Brute force $O(nk)$* -- For each window of size $k$, scan from left to right, maintain a running peak, and track the largest value of peak - prices[j]. Because the peak is only ever updated by earlier indices, the constraint that the peak precedes the trough is respected automatically. Append the per-window maximum to the result list.
*Faster $O(n \log k)$ (optional)* -- Max drawdown over an interval can be decomposed via a merge: each segment stores (its max drawdown, its prefix-max, its suffix-min); merging two segments gives dd = max(left.dd, right.dd, left.prefix_max - right.suffix_min). This makes it compatible with a segment tree, giving $O(n \log k)$ total time for all sliding windows. The brute-force version below is the reference implementation the judge checks.
Code:
```python def max_drawdown(prices, k): # For each sliding window of size k, return the maximum peak-to-trough # decline max(prices[i] - prices[j]) over indices i <= j inside the window. # Return a list of length len(prices) - k + 1. n = len(prices) result = [] for start in range(n - k + 1): peak = prices[start] max_dd = 0 for j in range(start, start + k): if prices[j] > peak: peak = prices[j] drop = peak - prices[j] if drop > max_dd: max_dd = drop result.append(max_dd) return result ```
Complexity: Brute force: $O(nk)$ time, $O(1)$ extra space (aside from the output list).
Answer: For each window, a single left-to-right pass tracking the running peak and the largest drop from it yields the window's max drawdown; collecting these gives the required list of length $n - k + 1$.
Intuition
Max drawdown is one of the most important risk metrics in quantitative finance -- it measures the worst peak-to-trough loss over a period. Computing it efficiently over sliding windows is a real production task: risk systems need to monitor rolling drawdowns across thousands of instruments in real time.
The algorithmic insight is that drawdown has a "mergeable" structure. Unlike some statistics (like median), you can combine drawdown information from two adjacent intervals efficiently. The cross-interval contribution is just the left side's max minus the right side's min, which is exactly what a segment tree is built to track. This same merge-based thinking applies to other rolling risk metrics like max run-up, peak-to-trough timing, and underwater duration.