Maximum Drawdown and Recovery Time
You are given a time series of cumulative P&L values $P_0, P_1, \ldots, P_n$. The drawdown at time $t$ is the drop from the running maximum to the current value:
$D_t = \max_{0 \le s \le t} P_s - P_t$
The maximum drawdown is $\max_t D_t$, and it occurs between some peak time $t_{\text{peak}}$ and trough time $t_{\text{trough}}$.
The recovery time after a trough is the number of steps until the cumulative P&L first reaches or exceeds the previous peak.
Design an algorithm that, in a single pass over the series ($O(n)$ time, $O(1)$ extra space), computes:
- The maximum drawdown magnitude and the dates $(t_{\text{peak}}, t_{\text{trough}})$ where it occurs.
- The shortest recovery time to a new high after any trough in the series.
Handle the edge case where the P&L never recovers to a previous high (i.e., recovery is undefined for the final drawdown).
Constraints: -
Example 1: ``` Input: P = [0, 5, 3, 8, 2, 9, 1] Output: max_drawdown = 8 (peak at t=5, trough at t=6) shortest_recovery = 1 ``` Explanation: The running max at each step is [0, 5, 5, 8, 8, 9, 9]. The drawdowns are [0, 0, 2, 0, 6, 0, 8]. The maximum drawdown of 8 occurs from the peak at $t=5$ (value 9) to the trough at $t=6$ (value 1). The trough at $t=6$ never recovers, so it is excluded from recovery time computation. The drawdown that begins at $t=2$ (peak was 5) recovers at $t=3$ (value 8 >= 5), recovery time = 1. The drawdown that begins at $t=4$ (peak was 8) recovers at $t=5$ (value 9 >= 8), recovery time = 1. Shortest recovery = 1.
Example 2: ``` Input: P = [10, 8, 6, 4] Output: max_drawdown = 6 (peak at t=0, trough at t=3) shortest_recovery = undefined (no recovery ever occurs) ```
Hints
- Think about what state you need to carry forward as you scan left to right. The drawdown at time $t$ depends only on the running maximum up to $t$.
- Track the running max in a single variable -- it only ever increases. When the current value drops below it, you are in a drawdown; when it meets or exceeds it, the drawdown has recovered.
- To find the shortest recovery, record the time each drawdown period starts (when P&L first drops below the running max) and compute the gap when it first returns to a new high.
Worked Solution
How to Think About It: This is a bread-and-butter risk metrics problem -- every trading desk computes max drawdown and recovery time daily. The key observation is that both metrics can be tracked with a single left-to-right scan if you maintain the right running state. You do not need to store the entire series of drawdowns or do any lookback. The trick is to recognize that drawdown at time $t$ depends only on the running max up to $t$, and recovery tracking just needs the current peak value and the time the last trough started.
Brute force would be $O(n^2)$: for each time $t$, scan backward to find the running max. But the running max is monotonically non-decreasing, so you can maintain it in a single variable. Recovery tracking is trickier -- you need to know when each drawdown period ends (i.e., when P&L returns to the previous peak). The insight is that you do not need to track all drawdowns simultaneously. You only need the current open drawdown (if any) and compare recovery times as each one closes.
Algorithm:
1. Initialize: running_max = P[0], peak_time = 0, max_dd = 0, best_peak = 0, best_trough = 0. 2. For tracking recovery: in_drawdown = false, dd_start_time = -1, shortest_recovery = infinity. 3. Scan $t = 1$ to $n$: - If $P_t \ge$ running_max: - If in_drawdown: this closes the current drawdown. Recovery time = $t -$ dd_start_time. Update shortest_recovery if smaller. - Update running_max = P[t], peak_time = t, in_drawdown = false. - Else (we are in a drawdown): - Compute dd = running_max - P[t]. - If dd > max_dd: update max_dd = dd, best_peak = peak_time, best_trough = t. - If not in_drawdown: mark in_drawdown = true, dd_start_time = t. 4. After the loop, if in_drawdown is still true, the final drawdown never recovered. Report recovery as undefined for that segment.
Subtlety on shortest recovery: The above tracks recovery from the start of each contiguous drawdown period to when the P&L first returns to the peak that started that drawdown. For the standard financial definition, recovery means returning to the previous high-water mark, measured from when the drawdown began.
Code: ```python def drawdown_stats(P): n = len(P) if n <= 1: return [0, 0, 0, -1]
running_max = P[0] peak_time = 0 max_dd = 0 best_peak = 0 best_trough = 0
in_dd = False dd_start = -1 shortest = None
for t in range(1, n): if P[t] >= running_max: if in_dd: rec = t - dd_start if shortest is None or rec < shortest: shortest = rec in_dd = False running_max = P[t] peak_time = t else: dd = running_max - P[t] if dd > max_dd: max_dd = dd best_peak = peak_time best_trough = t if not in_dd: in_dd = True dd_start = t
rec = shortest if shortest is not None else -1 return [max_dd, best_peak, best_trough, rec] ```
Complexity: $O(n)$ time (single pass), $O(1)$ extra space (only a handful of scalar variables regardless of input size).
Edge Cases: - Monotonically increasing series: max drawdown is 0, no recovery needed. - Monotonically decreasing series: max drawdown is $P_0 - P_n$, recovery is undefined (never reaches a new high). - Flat series: max drawdown is 0. - Series of length 1: max drawdown is 0.
Answer: Maintain a running maximum and track the current drawdown in a single left-to-right scan. The max drawdown is the largest gap between the running max and the current value. Recovery time is measured from the start of each drawdown period to when the P&L first returns to the running max. Both are computed in $O(n)$ time and $O(1)$ space. For P = [0, 5, 3, 8, 2, 9, 1] the result is max_drawdown = 8 (peak $t=5$, trough $t=6$) and shortest_recovery = 1.
Intuition
Maximum drawdown is the single most important risk metric on a trading desk -- it measures the worst peak-to-trough loss your strategy ever experienced. The reason it can be computed in a single pass is that drawdown is defined relative to the running maximum, which is monotonically non-decreasing. You never need to look backward: at each new time step, either you have set a new high (updating the running max and closing any open drawdown), or you are still below the previous peak (potentially deepening the current drawdown). This monotonicity is what makes the $O(1)$-space solution possible.
Recovery time adds a layer of practical importance: it tells you how long capital was underwater. A strategy with a 10% max drawdown that recovers in a week is very different from one that takes six months. In real systems, you would typically store the full drawdown curve for reporting, but the streaming single-pass version is what you would use in a live trading system that processes tick-by-tick P&L updates. The edge case where recovery never happens is not just academic -- it corresponds to a strategy that peaked and then died, which is exactly the scenario risk managers care most about flagging.