Arrays: Minimum swaps required to bring all elements less than or equal to k together

Problem Statement:

You are given an array and a number K.
You need to find the minimum number of swaps to bring all the numbers less than “k” together.

Example:

arr[] = {2, 1, 5, 6, 3}, k = 3
Output: 1

To bring [2, 1, 3] together, swap 5 with 3. So it can be done in one step.

Solution:

We can solve this problem by using two pointers and sliding window approach.

Below are the steps to solve the problem:

1. Find the count of elements that are less than the “k” value and store it as count.

2. Then get the number of elements that are greater than “k” in the window of size count and store it in a variable.

3. Repeat step 2, and take the min of the value continue till the end of array.

Example:

[1, 12, 10, 3, 5] k = 8
Number of elements <= k (k=8) ===> 3 (1,3,5)

Lets start sliding window,
[1, 12, 10, 3, 5] --- 2 elements>8 (12,10)
 |   |   |

[1, 12, 10, 3, 5] --- 2 elements>8 (12,10)
    |   |   |

[1, 12, 10, 3, 5] --- 1 elements>8 (10)
        |   |  |

Here if you swap [1, 10], the resultant array will be [10, 12, 1, 3, 5]. [1, 3, 5] are together.

Solution in C++

#include <vector>    
#include <algorithm>  
//visit www.ProDeveloperTutorial.com for 450+ solved questions  
#include <iostream>    
#include <queue>

using namespace std;

int min_swap(int *arr, int n, int k) 
{ 
      
    // get the count of elements which are less than equals to k 
    int count = 0; 
    for (int i = 0; i < n; ++i) 
        if (arr[i] <= k) 
            ++count; 
      
    // count the elements greater then k in first window of size=count
    int num_elem_greater_then_k = 0; 
    for (int i = 0; i < count; ++i) 
        if (arr[i] > k) 
            ++num_elem_greater_then_k; 
      
    // Initialize answer with 'num_elem_greater_then_k' value of current window 
    int ans = num_elem_greater_then_k; 
    for (int i = 0, j = count; j < n; ++i, ++j) { 
          
            //if element going out was greater than k then in the window we decrement the count
        if (arr[i] > k) 
            --num_elem_greater_then_k; 
          
            //if element coming in is greater than k then in the window we increment the count
        if (arr[j] > k) 
            ++num_elem_greater_then_k; 

        ans = min(ans, num_elem_greater_then_k); 
    } 
    return ans; 
} 
  
int main() 
{ 
      
    int arr[] = {1, 12, 10, 3, 5}; 
    int n = sizeof(arr) / sizeof(arr[0]); 
    int k = 3; 
    cout << min_swap(arr, n, k) << "\n"; 
      
    return 0; 
} 

Output:

1