Home » Data Structure » Array Data Structure

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

C++ implementation to find minimum swaps required to bring all elements less than or equal to k together.
Submitted by Vikneshwar GK, on March 04, 2022

Consider an integer array, of size n, and an integer k. The task at hand is to find the minimum number of swaps that are required to bring the array elements, that are lesser than or equal to k, together.

Example:

Input:
array[]= {2, 5, 4, 1, 6, 4}
k = 4

Output:
2

Explanation:
Elements less than or equal to 4 in the array are 2, 4, 1, 4.
Grouping the elements like {5, 2, 4, 1, 4, 6} will bring the 
elements together and it requires 2 swaps, (2, 5) and (6, 4)

Input:
array[]= {5, 1, 4, 6, 3, 7, 9}
k = 4

Output:
1

Solution:

This method involves identifying the subarray that contains the maximum number of elements whose values are lesser than or equal to k. The idea here is that difference of the total number of elements less than equal to k and the length of this subarray will give us the required solution.

• Count the number of elements whose value is less than or equal to k
• Find the maximum length subarray with elements less than or equal to k
• Find the difference between both and print

C++ Implementation:

#include <iostream>
using namespace std;

// Function to rearrange the array
int rearrangeArray(int array[], int length, int k)
{
    int countK = 0, window = 0, maxWindow = 0;

    for (int i = 0; i < length; i++) {

        if (array[i] <= k) {
            countK++;
            window++;
        }
        else {
            if (window > maxWindow) {
                maxWindow = window;
            }
            window = 0;
        }
    }

    return countK - maxWindow;
}

// Main function
int main()
{
    int array[100], N, k;
    
    cout << "Enter Number of elements: ";
    cin >> N;

    for (int i = 0; i < N; i++) {
        cout << "Enter element " << i + 1 << ": ";
        cin >> array[i];
    }

    cout << "Enter k: ";
    cin >> k;
    
    cout << rearrangeArray(array, N, k);
    
    return 0;
}

Output:

Enter Number of elements: 5
Enter element 1: 2
Enter element 2: 1
Enter element 3: 5
Enter element 4: 6
Enter element 5: 3
Enter k: 3
1

Time Complexity: O(n), where n is the length of the array.