Sliding Window Coding Problems: 71 Questions with Solutions

How sliding window works, step by step

1. The window is the stretch s[left..right], and it may never hold a character twice. Both edges start at index 0 with nothing inside yet; a map remembers the last index each character was seen at.
2. right moves to index 0 and reads 'p', which is not in the window, so the window grows to "p" (length 1). That is the longest yet: best = 1.
3. right moves to index 1 and reads 'w', which is not in the window, so the window grows to "pw" (length 2). That is the longest yet: best = 2.
4. right reaches 'w' at index 2, but 'w' is already in the window at index 1. Shrinking one step at a time would work, but the map says exactly where the repeat is.
5. So left jumps straight to index 2, one past the old 'w'. The window "w" is distinct again; its length is 1, and the best is still 2.
6. right moves to index 3 and reads 'k', which is not in the window, so the window grows to "wk" (length 2). The best stays 2.
7. right moves to index 4 and reads 'e', which is not in the window, so the window grows to "wke" (length 3). That is the longest yet: best = 3.
8. right reaches 'w' at index 5, but 'w' is already in the window at index 2. Shrinking one step at a time would work, but the map says exactly where the repeat is.
9. So left jumps straight to index 3, one past the old 'w'. The window "kew" is distinct again; its length is 3, and the best is still 3.
10. right has passed the end. Each index entered the window once and left at most once, so the scan is O(n) — the answer is 3, for "wke".

Sliding Window study plan

14 of the 71 Sliding Window problems (4 easy, 7 medium and 3 hard) over 8 days, about 8 h 10 min in all — the pattern first, then easiest to hardest. After that, the other 57 in the full list below are practice at your own pace. Then move on to Prefix Sum.

Day 1

Learn the pattern: read the essentials and step through the walkthrough above, then solve these 3.

• Minimum Difference Between Highest and Lowest of K Scores Easy
• Contains Duplicate II Easy
• Maximum Sum Subarray of Size K Easy

Day 2

Medium problems: the same pattern with one twist each. Name the twist before you code.

• Longest Harmonious Subsequence Easy
• Longest Substring Without Repeating Characters Medium

Day 3

More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

• Max Consecutive Ones III Medium
• Minimum Size Subarray Sum Medium

Day 4

More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

• Permutation in String Medium
• Longest Repeating Character Replacement Medium

Day 5

More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

• Find All Anagrams in a String Medium
• Fruit Into Baskets Medium

Day 6

Hard problems: the pattern combined with a second idea. Give each a full attempt before reading the editorial.

• Minimum Window Substring Hard

Day 7

Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.

• Sliding Window Maximum Hard

Day 8

Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.

• Max Value of Equation Hard

Next topic: Prefix Sum

Sliding Window: the essentials

When to reach for it

A contiguous subarray or substring with a condition on its contents that behaves monotonically: if a window is valid, so is every window inside it (for "longest") or every window around it (for "shortest"). "At most k distinct", "no repeated character", "sum at least the target, all values positive" and "every window of size k" all qualify. With negative numbers a sum condition is not monotone; use a Prefix Sum instead.

The pattern

Advance right one step at a time and add its element to the window's counters. While the window breaks the condition, remove nums[left] and advance left. Once it is valid again, [left, right] is the longest valid window ending at right. In the code below the left edge jumps straight past the earlier copy instead of stepping.

def longest_unique(s):
    last, left, best = {}, 0, 0
    for right, ch in enumerate(s):
        if last.get(ch, -1) >= left:    # a repeat inside the window
            left = last[ch] + 1
        last[ch] = right
        best = max(best, right - left + 1)
    return best

Cost

Each index enters and leaves the window at most once: O(n) time, with O(k) space for counters over k distinct values.

Common mistakes

• Window length off by one: [left, right] inclusive holds right - left + 1 elements.
• Recording the answer at the wrong moment: for "longest", after the window is valid again; for "shortest", inside the shrinking loop, while it is still valid.
• Leaving zero counts in a map and then using the map's size as the number of distinct values.
• Shrinking a window on sums that can go negative.

Start with

• Maximum Sum Subarray of Size K: a fixed-size window.
• Longest Substring Without Repeating Characters: a variable window, longest.
• Minimum Window Substring: a variable window, shortest, with counters.

All sliding window problems

Easy (13)

• Find the Power of K-Size Subarrays I Array
• Alternating Groups I Array
• Count Subarrays of Length Three With a Condition Array
• Minimum Recolors to Get K Consecutive Black Blocks String
• Defuse the Bomb Array, Simulation
• Substrings of Size Three with Distinct Characters String, Hash Table, Counting
• Find the K-Beauty of a Number Math, String
• Maximum Sum Subarray of Size K Array
• Shortest Subarray With OR at Least K I Bit Manipulation, Array
• Chocolate Distribution Problem Array, Sorting
• Minimum Difference Between Highest and Lowest of K Scores Array, Sorting
• Longest Harmonious Subsequence Array, Hash Table, Sorting
• Contains Duplicate II Array, Hash Table

Medium (43)

• Count Vowel Substrings of a String Hash Table, String
• Longest Substring of All Vowels in Order String
• Alternating Groups II Array
• Minimum Consecutive Cards to Pick Up Array, Hash Table
• Max Consecutive Ones II Array, Dynamic Programming
• Minimum Swaps to Group All 1's Together II Array
• Length of Longest Subarray With at Most K Frequency Array, Hash Table
• Maximum Beauty of an Array After Applying Operation Array, Sorting, Binary Search
• Count Complete Subarrays in an Array Array, Hash Table
• Number of Subarrays with Bounded Maximum Array, Two Pointers
• Count the Number of Good Subarrays Array, Hash Table, Counting
• Swap For Longest Repeated Character Substring String, Hash Table, Binary Search
• Replace the Substring for Balanced String String, Two Pointers
• Get Equal Substrings Within Budget String, Binary Search, Prefix Sum
• Maximize the Confusion of an Exam String, Prefix Sum, Binary Search
• Frequency of the Most Frequent Element Array, Greedy, Sorting
• K Radius Subarray Averages Array, Prefix Sum
• Maximum Points You Can Obtain from Cards Array, Prefix Sum
• Grumpy Bookstore Owner Array
• Number of Substrings Containing All Three Characters String, Hash Table
• Longest Substring with At Most K Distinct Characters String, Hash Table
• Longest Substring with At Most Two Distinct Characters String, Hash Table
• Longest Nice Subarray Bit Manipulation, Array
• Longest Substring With At Least K Repeating Characters String, Divide and Conquer
• Maximum Number of Occurrences of a Substring String, Hash Table
• Subarray With Given Sum Array, Two Pointers
• Longest Turbulent Subarray Array, Dynamic Programming
• Maximum Length of Repeated Subarray Array, Binary Search, Dynamic Programming
• Count Number of Nice Subarrays Array, Hash Table, Math
• Binary Subarrays With Sum Array, Hash Table, Prefix Sum
• Maximum Erasure Value Array, Hash Table
• Minimum Operations to Reduce X to Zero Array, Hash Table, Binary Search
• Longest Subarray of 1's After Deleting One Element Array, Dynamic Programming
• Subarray Product Less Than K Array, Binary Search, Prefix Sum
• Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold Array
• Maximum Number of Vowels in a Substring of Given Length String
• Permutation in String String, Hash Table
• Fruit Into Baskets Array, Hash Table
• Max Consecutive Ones III Array, Binary Search
• Minimum Size Subarray Sum Array, Prefix Sum
• Find All Anagrams in a String String, Hash Table
• Longest Repeating Character Replacement String
• Longest Substring Without Repeating Characters String, Hash Table

Hard (15)

• Constrained Subsequence Sum Array, Dynamic Programming, Queue
• Smallest Range Covering Elements from K Lists Array, Hash Table, Greedy
• Minimum Number of Operations to Make Array Continuous Array, Hash Table, Binary Search
• Minimum Number of Flips to Make the Binary String Alternating String, Dynamic Programming, Greedy
• Take K of Each Character From Left and Right String, Hash Table, Prefix Sum
• Minimum Number of K Consecutive Bit Flips Array, Prefix Sum, Greedy
• Shortest Subarray with Sum at Least K Array, Prefix Sum, Monotonic Queue
• Count Subarrays With Fixed Bounds Array, Two Pointers, Queue
• Maximum Number of Robots Within Budget Array, Two Pointers, Queue
• Minimum Window Subsequence String, Two Pointers, Dynamic Programming
• Subarrays with K Different Integers Array, Hash Table, Two Pointers
• Substring with Concatenation of All Words Hash Table, String
• Max Value of Equation Array, Monotonic Queue
• Sliding Window Maximum Array, Monotonic Queue, Heap
• Minimum Window Substring String, Hash Table

Companies that ask sliding window problems

• Amazon 61 problems on sliding window
• Google 48 problems on sliding window
• Microsoft 12 problems on sliding window
• Meta 7 problems on sliding window
• Adobe 6 problems on sliding window
• Flipkart 4 problems on sliding window
• Zoho 4 problems on sliding window
• Cognizant 3 problems on sliding window
• Infosys 3 problems on sliding window
• TCS 3 problems on sliding window
• Uber 3 problems on sliding window
• Accenture 2 problems on sliding window

Other topics

• Arrays 667 problems
• Strings 282 problems
• Math 213 problems
• Hash Table 202 problems
• Dynamic Programming 195 problems
• Greedy 163 problems
• Sorting 156 problems
• Two Pointers 113 problems
• Matrix 107 problems
• Binary Search 95 problems
• Simulation 88 problems
• Bit Manipulation 83 problems