Loading...
Tier I · Fundamentals
Maintaining a moving subarray or substring while its invariant holds.
A window is a contiguous range of an array or string. It grows at the right end, shrinks at the left, and never moves backward, so every element enters once and leaves once.
Find the longest run of neighbors whose sum is at most 7. The window starts empty.
The right edge adds one element at a time. Whenever the window breaks the rule, the left edge drops elements until it holds again, and the best size seen so far is the answer.
| Variant | Window size | Typical question |
|---|---|---|
| Fixed | Always | Best sum or count over any consecutive elements |
| Grow and shrink | Changes as you go | Longest or shortest range that satisfies a rule |
| Counting | Changes as you go | How many ranges satisfy a rule |
The window's state (a sum, a count, a map of counts) must be cheap to update when one element enters and one leaves. Sums and counts are. A running max or min is not, and needs the monotonic deque covered in a later category.
| Approach | Time | Extra space |
|---|---|---|
| Check every subarray | or worse | |
| Window with a sum or count | ||
| Window with a map of counts | , distinct values |
Use it for "longest", "shortest", or "how many" questions about contiguous subarrays and substrings. The whole technique is deciding when to grow, when to shrink, and when to record the answer.
The problems below start with fixed-size windows, move to windows whose state is a count and then a map, and end with counting windows and finding the shortest one.
Recommended first: Two Pointers, Hash Maps.
You've cleared 0 of 17 problems in these. You can dive in anyway.