LeetCode 239 Sliding Window Maximum - Why Naive Fails

For each window position, scan all k elements to find the maximum.

There are $n - k + 1$ windows. Scanning each takes $O(k)$. Total: $O(nk)$.

For $n = 10^5$ and $k = 10^4$, that's $10^9$ operations. Too slow.