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

Given an array of n positive integers and a number **k**. Find the **minimum** number of swaps required to bring all the numbers less than or equal to **k** together.

Input:arr[] = {2, 1, 5, 6, 3}, k = 3Output:1Explanation:To bring elements 2, 1, 3 together, swap element '5' with '3' such that final array will be- arr[] = {2, 1, 3, 6, 5}Input:arr[] = {2, 7, 9, 5, 8, 7, 4}, k = 5Output:2

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.

A **simple solution** is to first count all elements less than or equals to **k**(say ‘good’). Now traverse for every sub-array and swap those elements whose value is greater than **k**. Time complexity of this approach is O(n^{2})

A **simple approach** is to use two pointer technique and sliding window.

- Find count of all elements which are less than or equals to ‘k’. Let’s say the count is ‘cnt’
- Using two pointer technique for window of length ‘cnt’, each time keep track of how many elements in this range are greater than ‘k’. Let’s say the total count is ‘bad’.
- Repeat step 2, for every window of length ‘cnt’ and take minimum of count ‘bad’ among them. This will be the final answer.

## C++

`// C++ program to find minimum swaps required` `// to club all elements less than or equals` `// to k together` `#include <iostream>` `using` `namespace` `std;` `// Utility function to find minimum swaps` `// required to club all elements less than` `// or equals to k together` `int` `minSwap(` `int` `*arr, ` `int` `n, ` `int` `k) {` ` ` ` ` `// Find 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;` ` ` ` ` `// Find unwanted elements in current` ` ` `// window of size 'count'` ` ` `int` `bad = 0;` ` ` `for` `(` `int` `i = 0; i < count; ++i)` ` ` `if` `(arr[i] > k)` ` ` `++bad;` ` ` ` ` `// Initialize answer with 'bad' value of` ` ` `// current window` ` ` `int` `ans = bad;` ` ` `for` `(` `int` `i = 0, j = count; j < n; ++i, ++j) {` ` ` ` ` `// Decrement count of previous window` ` ` `if` `(arr[i] > k)` ` ` `--bad;` ` ` ` ` `// Increment count of current window` ` ` `if` `(arr[j] > k)` ` ` `++bad;` ` ` ` ` `// Update ans if count of 'bad'` ` ` `// is less in current window` ` ` `ans = min(ans, bad);` ` ` `}` ` ` `return` `ans;` `}` `// Driver code` `int` `main() {` ` ` ` ` `int` `arr[] = {2, 1, 5, 6, 3};` ` ` `int` `n = ` `sizeof` `(arr) / ` `sizeof` `(arr[0]);` ` ` `int` `k = 3;` ` ` `cout << minSwap(arr, n, k) << ` `"\n"` `;` ` ` ` ` `int` `arr1[] = {2, 7, 9, 5, 8, 7, 4};` ` ` `n = ` `sizeof` `(arr1) / ` `sizeof` `(arr1[0]);` ` ` `k = 5;` ` ` `cout << minSwap(arr1, n, k);` ` ` `return` `0;` `}` |

## Java

`// Java program to find minimum` `// swaps required to club all` `// elements less than or equals` `// to k together` `import` `java.lang.*;` `class` `GFG {` ` ` `// Utility function to find minimum swaps` `// required to club all elements less than` `// or equals to k together` `static` `int` `minSwap(` `int` `arr[], ` `int` `n, ` `int` `k) {` ` ` `// Find 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;` ` ` `// Find unwanted elements in current` ` ` `// window of size 'count'` ` ` `int` `bad = ` `0` `;` ` ` `for` `(` `int` `i = ` `0` `; i < count; ++i)` ` ` `if` `(arr[i] > k)` ` ` `++bad;` ` ` `// Initialize answer with 'bad' value of` ` ` `// current window` ` ` `int` `ans = bad;` ` ` `for` `(` `int` `i = ` `0` `, j = count; j < n; ++i, ++j) {` ` ` `// Decrement count of previous window` ` ` `if` `(arr[i] > k)` ` ` `--bad;` ` ` `// Increment count of current window` ` ` `if` `(arr[j] > k)` ` ` `++bad;` ` ` `// Update ans if count of 'bad'` ` ` `// is less in current window` ` ` `ans = Math.min(ans, bad);` ` ` `}` ` ` `return` `ans;` `}` `// Driver code` `public` `static` `void` `main(String[] args)` `{` ` ` `int` `arr[] = {` `2` `, ` `1` `, ` `5` `, ` `6` `, ` `3` `};` ` ` `int` `n = arr.length;` ` ` `int` `k = ` `3` `;` ` ` `System.out.print(minSwap(arr, n, k) + ` `"\n"` `);` ` ` `int` `arr1[] = {` `2` `, ` `7` `, ` `9` `, ` `5` `, ` `8` `, ` `7` `, ` `4` `};` ` ` `n = arr1.length;` ` ` `k = ` `5` `;` ` ` `System.out.print(minSwap(arr1, n, k));` `}` `}` `// This code is contributed by Anant Agarwal.` |

## Python3

`# Python3 program to find` `# minimum swaps required` `# to club all elements less` `# than or equals to k together` `# Utility function to find` `# minimum swaps required to` `# club all elements less than` `# or equals to k together` `def` `minSwap(arr, n, k) :` ` ` ` ` `# Find count of elements` ` ` `# which are less than` ` ` `# equals to k` ` ` `count ` `=` `0` ` ` `for` `i ` `in` `range` `(` `0` `, n) :` ` ` `if` `(arr[i] <` `=` `k) :` ` ` `count ` `=` `count ` `+` `1` ` ` ` ` `# Find unwanted elements` ` ` `# in current window of` ` ` `# size 'count'` ` ` `bad ` `=` `0` ` ` `for` `i ` `in` `range` `(` `0` `, count) :` ` ` `if` `(arr[i] > k) :` ` ` `bad ` `=` `bad ` `+` `1` ` ` ` ` `# Initialize answer with` ` ` `# 'bad' value of current` ` ` `# window` ` ` `ans ` `=` `bad` ` ` `j ` `=` `count` ` ` `for` `i ` `in` `range` `(` `0` `, n) :` ` ` ` ` `if` `(j ` `=` `=` `n) :` ` ` `break` ` ` ` ` `# Decrement count of` ` ` `# previous window` ` ` `if` `(arr[i] > k) :` ` ` `bad ` `=` `bad ` `-` `1` ` ` ` ` `# Increment count of` ` ` `# current window` ` ` `if` `(arr[j] > k) :` ` ` `bad ` `=` `bad ` `+` `1` ` ` ` ` `# Update ans if count` ` ` `# of 'bad' is less in` ` ` `# current window` ` ` `ans ` `=` `min` `(ans, bad)` ` ` `j ` `=` `j ` `+` `1` ` ` `return` `ans` `# Driver code` `arr ` `=` `[` `2` `, ` `1` `, ` `5` `, ` `6` `, ` `3` `]` `n ` `=` `len` `(arr)` `k ` `=` `3` `print` `(minSwap(arr, n, k))` `arr1 ` `=` `[` `2` `, ` `7` `, ` `9` `, ` `5` `, ` `8` `, ` `7` `, ` `4` `]` `n ` `=` `len` `(arr1)` `k ` `=` `5` `print` `(minSwap(arr1, n, k))` `# This code is contributed by` `# Manish Shaw(manishshaw1)` |

## C#

`// C# program to find minimum` `// swaps required to club all` `// elements less than or equals` `// to k together` `using` `System;` `class` `GFG {` ` ` ` ` `// Utility function to find minimum swaps` ` ` `// required to club all elements less than` ` ` `// or equals to k together` ` ` `static` `int` `minSwap(` `int` `[]arr, ` `int` `n, ` `int` `k) {` ` ` ` ` `// Find 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;` ` ` ` ` `// Find unwanted elements in current` ` ` `// window of size 'count'` ` ` `int` `bad = 0;` ` ` `for` `(` `int` `i = 0; i < count; ++i)` ` ` `if` `(arr[i] > k)` ` ` `++bad;` ` ` ` ` `// Initialize answer with 'bad' value of` ` ` `// current window` ` ` `int` `ans = bad;` ` ` `for` `(` `int` `i = 0, j = count; j < n; ++i, ++j) {` ` ` ` ` `// Decrement count of previous window` ` ` `if` `(arr[i] > k)` ` ` `--bad;` ` ` ` ` `// Increment count of current window` ` ` `if` `(arr[j] > k)` ` ` `++bad;` ` ` ` ` `// Update ans if count of 'bad'` ` ` `// is less in current window` ` ` `ans = Math.Min(ans, bad);` ` ` `}` ` ` `return` `ans;` ` ` `}` ` ` ` ` `// Driver code` ` ` `public` `static` `void` `Main()` ` ` `{` ` ` `int` `[]arr = {2, 1, 5, 6, 3};` ` ` `int` `n = arr.Length;` ` ` `int` `k = 3;` ` ` `Console.WriteLine(minSwap(arr, n, k));` ` ` ` ` `int` `[]arr1 = {2, 7, 9, 5, 8, 7, 4};` ` ` `n = arr1.Length;` ` ` `k = 5;` ` ` `Console.WriteLine(minSwap(arr1, n, k));` ` ` `}` `}` `// This code is contributed by vt_m.` |

## PHP

`<?php` `// PHP program to find` `// minimum swaps required` `// to club all elements` `// less than or equals` `// to k together` `// Utility function to` `// find minimum swaps` `// required to club all` `// elements less than` `// or equals to k together` `function` `minSwap(` `$arr` `, ` `$n` `, ` `$k` `)` `{` ` ` ` ` `// Find count of elements` ` ` `// which are less than` ` ` `// equals to k` ` ` `$count` `= 0;` ` ` `for` `(` `$i` `= 0; ` `$i` `< ` `$n` `; ++` `$i` `)` ` ` `if` `(` `$arr` `[` `$i` `] <= ` `$k` `)` ` ` `++` `$count` `;` ` ` ` ` `// Find unwanted elements in current` ` ` `// window of size 'count'` ` ` `$bad` `= 0;` ` ` `for` `(` `$i` `= 0; ` `$i` `< ` `$count` `; ++` `$i` `)` ` ` `if` `(` `$arr` `[` `$i` `] > ` `$k` `)` ` ` `++` `$bad` `;` ` ` ` ` `// Initialize answer` ` ` `// with 'bad' value of` ` ` `// current window` ` ` `$ans` `= ` `$bad` `;` ` ` `for` `(` `$i` `= 0, ` `$j` `= ` `$count` `; ` `$j` `< ` `$n` `;` ` ` `++` `$i` `, ++` `$j` `)` ` ` `{` ` ` ` ` `// Decrement count of` ` ` `// previous window` ` ` `if` `(` `$arr` `[` `$i` `] > ` `$k` `)` ` ` `--` `$bad` `;` ` ` ` ` `// Increment count of` ` ` `// current window` ` ` `if` `(` `$arr` `[` `$j` `] > ` `$k` `)` ` ` `++` `$bad` `;` ` ` ` ` `// Update ans if count of 'bad'` ` ` `// is less in current window` ` ` `$ans` `= min(` `$ans` `, ` `$bad` `);` ` ` `}` ` ` `return` `$ans` `;` `}` `// Driver code` `$arr` `= ` `array` `(2, 1, 5, 6, 3);` `$n` `= sizeof(` `$arr` `);` `$k` `= 3;` `echo` `(minSwap(` `$arr` `, ` `$n` `, ` `$k` `) . ` `"\n"` `);` ` ` `$arr1` `= ` `array` `(2, 7, 9, 5, 8, 7, 4);` `$n` `= sizeof(` `$arr1` `);` `$k` `= 5;` `echo` `(minSwap(` `$arr1` `, ` `$n` `, ` `$k` `));` `// This code is contributed by Ajit.` `?>` |

## Javascript

`<script>` `// Utility function to find minimum swaps` `// required to club all elements less than` `// or equals to k together` `function` `minSwap(arr, n, k) {` ` ` ` ` `// Find count of elements which are` ` ` `// less than equals to k` ` ` `var` `count = 0;` ` ` `for` `(` `var` `i = 0; i < n; ++i)` ` ` `if` `(arr[i] <= k)` ` ` `++count;` ` ` ` ` `// Find unwanted elements in current` ` ` `// window of size 'count'` ` ` `var` `bad = 0;` ` ` `for` `(` `var` `i = 0; i < count; ++i)` ` ` `if` `(arr[i] > k)` ` ` `++bad;` ` ` ` ` `// Initialize answer with 'bad' value of` ` ` `// current window` ` ` `var` `ans = bad;` ` ` `for` `(` `var` `i = 0, j = count; j < n; ++i, ++j) {` ` ` ` ` `// Decrement count of previous window` ` ` `if` `(arr[i] > k)` ` ` `--bad;` ` ` ` ` `// Increment count of current window` ` ` `if` `(arr[j] > k)` ` ` `++bad;` ` ` ` ` `// Update ans if count of 'bad'` ` ` `// is less in current window` ` ` `ans = Math.min(ans, bad);` ` ` `}` ` ` `return` `ans;` `}` ` ` `// Driver code` ` ` `var` `arr=[2, 1, 5, 6, 3];` ` ` `var` `n =5;` ` ` `var` `k = 3;` ` ` `document.write(minSwap(arr, n, k) + ` `"<br>"` `);` ` ` ` ` `var` `arr1 = [2, 7, 9, 5, 8, 7, 4];` ` ` `n = 7;` ` ` `k = 5;` ` ` `document.write(minSwap(arr1, n, k));` `// This code is by Akshit Nikita Saxena` `</script>` |