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 | |

Sliding window with fixed size | Watch out when sliding windows doesn’t have enough elements |

Sliding window with non-decreasing size | |

Sliding window with adjustable size |

**Scenarios**

**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 }

**Questions**

Name | Example |
---|---|

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

The of size sliding window is non-fixed, but growing | Leetcode: Max Consecutive Ones III |

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

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

Inspiring sliding window problem | Leetcode: Moving Stones Until Consecutive II |

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: 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 Average Subarray II
- Leetcode: Maximum Average Subarray I
- Leetcode: Max Consecutive Ones III
- Leetcode: Max Chunks To Make Sorted
- 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: Get Equal Substrings Within Budget
- Leetcode: Find K-th Smallest Pair Distance
- Leetcode: Diet Plan Performance
- Leetcode: Contains Duplicate II

See more blog_posts.