Skip to content
ComplexityX

Settings

Server engine

Loading…

Use my own key optional

The key stays in this browser's local storage and is sent only to this app's /api/analyze route, which forwards it to the provider. It is never stored on the server.

All patterns

Sliding Window

Grow and shrink a contiguous range while keeping a running summary.

time O(n)space O(1) to O(k)

What it is

Maintain a window [left, right] over a sequence. Extend right to include more, shrink left when a constraint breaks. Every index enters and leaves the window at most once, so the inner while loop is amortized O(1) per step.

When to reach for it

  • Longest or shortest contiguous subarray or substring with a property
  • Fixed size k windows (max sum, averages)
  • Counting distinct elements in a range

Clues in the problem

  • “Contiguous”, “substring”, “subarray”
  • Condition becomes monotone as the window grows (all values non-negative, or a distinct-count limit)
  • Nested loop where the inner start never needs to reset

Template

def longest_valid(a):
left = best = 0
state = {} # counts, running sum, ...
for right, x in enumerate(a):
state[x] = state.get(x, 0) + 1
while violates(state): # shrink until valid again
state[a[left]] -= 1
left += 1
best = max(best, right - left + 1)
return best

Practice problems

  • Longest Substring Without Repeating Characters
  • Minimum Size Subarray Sum
  • Maximum Sum Subarray of Size K
  • Fruit Into Baskets

Common mistakes

  • Using it when values can be negative and the sum is not monotone (use prefix sums instead)
  • Forgetting to update state when left moves
  • Recomputing the window contents from scratch each step