Review: Slidingwindow Problems

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

• CheatSheet: Leetcode For Code Interview
• CheatSheet: Common Code Problems & Follow-ups

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.