Saidul Islam RajibThe sliding window, four patterns deep
Turning O(n·k) into O(n) by not throwing away work you already did
Key takeaways
- When windows overlap, do not rebuild them — update them.
- The inner while loop is still O(n): left only ever moves forward.
- Contiguous means window; subsequence does not.
Most array problems have an obvious brute force answer: check every window, take the best one. It works, and it is O(n·k). Consecutive windows overlap almost completely. Only one e…