Slidingwindow Problems

**Basic Abstractions**

Name | Summary |
---|---|

Move right pointer | l+k-1 (l: left, k: window length) |

Move left pointer | r-k+1 (r: right, k: window length) |

Collect results | r-k+1>=0 |

Make sure neither pointers will go backwards |

**Scenarios**

**Top Questions**

Num | Problem | Summary |
---|---|---|

1 | Sliding window with fixed size | LeetCode: Find All Anagrams in a String |

2 | Sliding window with non-decreasing size | LeetCode: Max Consecutive Ones III |

3 | How to initialize the time window? | LeetCode: Minimum Swaps to Group All 1’s Together |

4 | Sliding window with non-decreasing size | LeetCode: Max Consecutive Ones III |

5 | Move two pointers: two loop vs One loop | LeetCode: Longest Substring Without Repeating Characters |

6 | Inspiring sliding window problem | LeetCode: Moving Stones Until Consecutive II |

7 | Sliding window with lazy removal | Leetcode: Sliding Window Median |

8 | Sliding window with adjustable size | |

9 | Move pointer1 to match the other, or the other way around |

**Code Skeleton**

- Sliding window with fixed size

// Blog link: https://code.dennyzhang.com/minimum-swaps-to-group-all-1s-together // Basic Ideas: fixed size sliding window // We know the size of the final group all 1's // The window can start from any position // Use a sliding window. And the find the minimum count of 0s in the sliding window. // Complexity: Time O(n), Space O(k) func minSwaps(data []int) int { k:=0 for _, v := range data { if v == 1 { k++ } } res := 1<<31-1 count := 0 // sliding window. left: i-k+1, right: i for i:=0; i<len(data); i++ { // move right pointer: add a new element if data[i] == 0 { count++ } // move left pointer: remove the old element if i-k >= 0 { if data[i-k] == 0 { count-- } } // collect result if i-k+1 >= 0 { if count < res { res = count } } } return res }

See all slidingwindow problems: #slidingwindow

- Review: Slidingwindow Problems
- LeetCode: Video Stitching
- LeetCode: Twitch Words
- LeetCode: Swap For Longest Repeated Character Substring
- LeetCode: Subarrays with K Different Integers
- LeetCode: Sliding Window Median
- LeetCode: Sliding Window Maximum
- LeetCode: Shortest Way to Form String
- LeetCode: Permutation in String
- LeetCode: Number of Substrings Containing All Three Characters
- LeetCode: Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold
- LeetCode: Moving Stones Until Consecutive II
- LeetCode: Minimum Window Substring
- LeetCode: Minimum Swaps to Group All 1’s Together
- LeetCode: Minimum Number of Taps to Open to Water a Garden
- LeetCode: Maximum Number of Vowels in a Substring of Given Length
- LeetCode: Maximum Average Subarray II
- LeetCode: Maximum Average Subarray I
- LeetCode: Max Consecutive Ones III
- LeetCode: Max Chunks To Make Sorted
- LeetCode: Longest Turbulent Subarray
- LeetCode: Longest Substring Without Repeating Characters
- LeetCode: Longest Substring with At Most Two Distinct Characters
- LeetCode: Longest Substring with At Most K Distinct Characters
- LeetCode: Longest Repeating Character Replacement
- LeetCode: Grumpy Bookstore Owner
- LeetCode: Get Equal Substrings Within Budget
- LeetCode: Find K-th Smallest Pair Distance
- LeetCode: Find All Anagrams in a String
- LeetCode: Diet Plan Performance
- LeetCode: Count Substrings with Only One Distinct Letter
- LeetCode: Contains Duplicate II
- LeetCode: Constrained Subset Sum
- LeetCode: Check If a String Contains All Binary Codes of Size K

See more blog posts.