Python – Find the Minimum Swaps Required to Bring Elements ≤ k Together

This problem is a common question in data structures and algorithms interviews. The goal is to rearrange an array such that all elements less than or equal to a given value k are grouped together with the minimum number of swaps.

Problem Statement

Given an array arr and a number k, determine the minimum number of swaps required to bring all the elements less than or equal to k together in the array.

Sample Input and Output

Example 1:

</>
Copy
Input: arr = [2, 7, 9, 5, 8, 7, 4], k = 5
Output: 2
Explanation: Elements ≤ 5 are [2, 5, 4]. Minimum swaps required = 2

Example 2:

</>
Copy
Input: arr = [1, 12, 10, 3, 14, 10, 5], k = 8
Output: 2
Explanation: Elements ≤ 8 are [1, 3, 5]. Minimum swaps required = 2

Solution Approach

We can solve this problem using a sliding window approach:

  1. Count the “Good” Elements: Count all elements in the array that are less than or equal to k. Let this count be good_count. This determines the size of the window we need.
  2. Calculate the Initial “Bad” Count: In the first window (of size good_count), count the number of elements greater than k (considered “bad”). This count represents the number of swaps needed for this window.
  3. Slide the Window: Move the window one element at a time through the array. For each new window, update the count by subtracting the element that is left behind and adding the new element. Maintain the minimum “bad” count seen across all windows.
  4. Result: The minimum count of “bad” elements found in any window is the minimum number of swaps required to group all elements ≤ k together.

Python Program

</>
Copy
def min_swaps_to_group(arr, k):
    # Count elements that are less than or equal to k
    good_count = sum(1 for num in arr if num <= k)
    
    # Count 'bad' elements (elements greater than k) in the initial window of size good_count
    bad = sum(1 for num in arr[:good_count] if num > k)
    
    # Initialize minimum swaps with the 'bad' count of the first window
    min_swaps = bad
    
    # Slide the window from index 1 to (len(arr) - good_count)
    for i in range(1, len(arr) - good_count + 1):
        # If the element leaving the window is 'bad', decrease the count
        if arr[i - 1] > k:
            bad -= 1
        # If the new element entering the window is 'bad', increase the count
        if arr[i + good_count - 1] > k:
            bad += 1
        # Update the minimum swaps required if the current window has fewer 'bad' elements
        min_swaps = min(min_swaps, bad)
        
    return min_swaps

# Example 1
arr1 = [2, 7, 9, 5, 8, 7, 4]
k1 = 5
print("Minimum swaps required:", min_swaps_to_group(arr1, k1))  # Output: 2

# Example 2
arr2 = [1, 12, 10, 3, 14, 10, 5]
k2 = 8
print("Minimum swaps required:", min_swaps_to_group(arr2, k2))  # Output: 2

Conclusion

This tutorial explained how to solve the problem of finding the minimum swaps required to group all elements less than or equal to a given value k together in an array. By counting the number of desired elements and using a sliding window technique, we can efficiently determine the optimal number of swaps needed.