TRT
Sign in

Advanced · Module 14 · Lesson 2 of 4

Sliding window

A window over a contiguous range grows on the right and shrinks on the left, with both ends only ever moving forward. Keeping a summary of the window up to date turns many O(n²) substring and subarray searches into O(n).

Pro — members onlyAbout 15 minutes

By the end you can

  • Maintain a fixed-size window and a variable-size window over an array or string
  • Keep the window's state, such as a sum or a count of characters, up to date in O(1) per step
  • Explain when shrinking the window is safe, and recognize problems where a window doesn't work

Builds on Two pointers.

01 · A question first

Find the longest stretch of a string with no repeated character. There are about n²/2 substrings, and checking one for repeats takes O(n). A window that grows on the right and shrinks on the left finds the answer in one pass. When is it safe to shrink, and why does that never lose the answer?

Make a guess before you read on.

02 · The idea

Members only

Unlock the full lesson

This lesson is part of the membership. Join to read it in full, along with every other premium deep dive.

What's inside

  • Windows over contiguous data
  • Fixed-size windows
  • Variable-size windows
  • When shrinking is safe
  • Counting windows
  • A single pass with a running minimum
  • Choosing the summary
  • Pseudocode & Multi-Language Implementations (C++, Java, Python)
See plansAlready a member? Sign in

03 · Practice

Practice · easy · LeetCodeBest Time to Buy and Sell StockChoose one buy day and a later sell day to maximize positive profit; return zero if no profitable trade exists.Practice · medium · LeetCodeLongest Substring Without Repeating CharactersFind the maximum length of a contiguous substring containing no repeated characters.Practice · medium · LeetCodeLongest Repeating Character ReplacementFind the longest substring that can be made uniform by replacing at most k characters.Practice · medium · LeetCodePermutation in StringDetermine whether any contiguous window in the second string is a permutation of the first string.Practice · hard · LeetCodeMinimum Window SubstringFind the shortest substring of s containing every required character in t with at least its required multiplicity.

Asked in interviews

Something wrong with this lesson? Report a problem