Lecture Notes: Sliding Window Problem 25

Introduction

• Welcome to the channel "Code Sari with Mike"
• Video number 25 in the sliding window playlist
• Correction: Previous video was actually the 24th, not 34th

Problem Definition

• Problem Statement: Minimum swaps to group all 1's together in a circular array.
• This problem has been asked by companies like Microsoft.
• Definitions:
  • Swap: Taking two distinct positions and swapping their values.
  • Circular Array: First and last elements are considered adjacent.

Example Analysis

• Given a binary circular array, find minimum swaps required to group all 1's together.
• Example: If swapping positions leads to all 1's together with minimal swaps, that is the target.

Sample Scenario

1. Example 1: A single swap can achieve the goal:

   • Swap two indexes to gather all 1's together.
   • Result: All 1's are grouped with one swap.

2. Example 2: Requires two swaps:

   • Swap two different pairs to group 1's.
   • Result: All 1's are successfully grouped.

3. Example 3: No swaps required:

   • 1's are already grouped together due to circular nature.

Thought Process

• Primary requirement: Gather all 1's in one location.
• Total 1's to gather (e.g., 5 in an example).
• Window Size: Size of the sliding window equals the number of 1's.
• Determine how many additional swaps are needed based on the current window's 1's count.
• Aim to maximize the current window's count of 1's to minimize swaps.

Sliding Window Approach

• Sliding Window Size: Set to total count of 1's.
• Current Count Calculation: Determine how many 1's are present in the current window.
• Max Count: Keep track of the maximum count of 1's found in any window.
• Swap Calculation: Swaps required = Total 1's - Maximum current 1's.

Circular Array Handling

• To handle the circular nature:
  • Duplicate the original input array (append it to itself).
  • Use a normal sliding window approach on the doubled array.
• This method helps manage wrap-around situations easily.

Code Strategy

1. Use an array of size 2n (where n is the original array size).
2. Iterate through the first 2n elements, maintaining a sliding window.
3. Calculate the total number of 1's in the original array.
4. If the current window exceeds the size containing all 1's, adjust by subtracting from the count.
5. Return the minimum swaps required.

Improved Implementation (Without Extra Space)

• Adjust previous implementation to avoid additional array duplication.
• Use modular arithmetic to handle circular indexing when accessing the original array elements.
• Maintain the current count of 1's without needing an extra space.

Conclusion

• Successfully addressed the sliding window problem in a circular array.
• Efficiently calculated minimum swaps required using both space and non-space methods.
• Encourage viewers to comment for any doubts or further clarifications.

Next Steps

• Code demonstration in the next video to solidify understanding.