# Minimum number of adjacent swaps for arranging similar elements together

Given an array of 2 * N positive integers where each array element lies between 1 to N and appears exactly twice in the array. The task is to find the minimum number of adjacent swaps required to arrange all similar array elements together.**Note**: It is not necessary that the final array (after performing swaps) should be sorted.**Examples:**

Input: arr[] = { 1, 2, 3, 3, 1, 2 }

Output: 5

After first swapping, array will be arr[] = { 1, 2, 3, 1, 3, 2 },

after second arr[] = { 1, 2, 1, 3, 3, 2 }, after third arr[] = { 1, 1, 2, 3, 3, 2 },

after fourth arr[] = { 1, 1, 2, 3, 2, 3 }, after fifth arr[] = { 1, 1, 2, 2, 3, 3 }

Input: arr[] = { 1, 2, 1, 2 }

Output: 1

arr[2] can be swapped with arr[1] to get the required position.

**Approach**: This problem can be solved using greedy approach. Following are the steps :

- Keep an array
*visited[]*which tells that visited[curr_ele] is false if swap operation has not been performed on curr_ele. - Traverse through the original array and if the current array element has not been visited yet i.e.
*visited[arr[curr_ele]] = false*, set it to true and iterate over another loop starting from the current position to the end of array. - Initialize a variable count which will determine the number of swaps required to place the current element’s partner at its correct position.
- In nested loop, increment count only if the visited[curr_ele] is false (since if it is true, means curr_ele has already been placed at its correct position).
- If the current element’s partner is found in the nested loop, add up the value of count to the total answer.

Below is the implementation of above approach:

## C++

`// C++ Program to find the minimum number of` `// adjacent swaps to arrange similar items together` `#include <bits/stdc++.h>` `using` `namespace` `std;` `// Function to find minimum swaps` `int` `findMinimumAdjacentSwaps(` `int` `arr[], ` `int` `N)` `{` ` ` `// visited array to check if value is seen already` ` ` `bool` `visited[N + 1];` ` ` `int` `minimumSwaps = 0;` ` ` `memset` `(visited, ` `false` `, ` `sizeof` `(visited));` ` ` `for` `(` `int` `i = 0; i < 2 * N; i++) {` ` ` `// If the arr[i] is seen first time` ` ` `if` `(visited[arr[i]] == ` `false` `) {` ` ` `visited[arr[i]] = ` `true` `;` ` ` `// stores the number of swaps required to` ` ` `// find the correct position of current` ` ` `// element's partner` ` ` `int` `count = 0;` ` ` `for` `(` `int` `j = i + 1; j < 2 * N; j++) {` ` ` `// Increment count only if the current` ` ` `// element has not been visited yet (if is` ` ` `// visited, means it has already been placed` ` ` `// at its correct position)` ` ` `if` `(visited[arr[j]] == ` `false` `)` ` ` `count++;` ` ` `// If current element's partner is found` ` ` `else` `if` `(arr[i] == arr[j])` ` ` `minimumSwaps += count;` ` ` `}` ` ` `}` ` ` `}` ` ` `return` `minimumSwaps;` `}` `// Driver Code` `int` `main()` `{` ` ` `int` `arr[] = { 1, 2, 3, 3, 1, 2 };` ` ` `int` `N = ` `sizeof` `(arr) / ` `sizeof` `(arr[0]);` ` ` `N /= 2;` ` ` `cout << findMinimumAdjacentSwaps(arr, N) << endl;` ` ` `return` `0;` `}` |

## Java

`// Java Program to find the minimum number of` `// adjacent swaps to arrange similar items together` `import` `java.util.*;` `class` `solution` `{` `// Function to find minimum swaps` `static` `int` `findMinimumAdjacentSwaps(` `int` `arr[], ` `int` `N)` `{` ` ` `// visited array to check if value is seen already` ` ` `boolean` `[] visited = ` `new` `boolean` `[N + ` `1` `];` ` ` `int` `minimumSwaps = ` `0` `;` ` ` `Arrays.fill(visited,` `false` `);` ` ` ` ` `for` `(` `int` `i = ` `0` `; i < ` `2` `* N; i++) {` ` ` `// If the arr[i] is seen first time` ` ` `if` `(visited[arr[i]] == ` `false` `) {` ` ` `visited[arr[i]] = ` `true` `;` ` ` `// stores the number of swaps required to` ` ` `// find the correct position of current` ` ` `// element's partner` ` ` `int` `count = ` `0` `;` ` ` `for` `(` `int` `j = i + ` `1` `; j < ` `2` `* N; j++) {` ` ` `// Increment count only if the current` ` ` `// element has not been visited yet (if is` ` ` `// visited, means it has already been placed` ` ` `// at its correct position)` ` ` `if` `(visited[arr[j]] == ` `false` `)` ` ` `count++;` ` ` `// If current element's partner is found` ` ` `else` `if` `(arr[i] == arr[j])` ` ` `minimumSwaps += count;` ` ` `}` ` ` `}` ` ` `}` ` ` `return` `minimumSwaps;` `}` `// Driver Code` `public` `static` `void` `main(String args[])` `{` ` ` `int` `arr[] = { ` `1` `, ` `2` `, ` `3` `, ` `3` `, ` `1` `, ` `2` `};` ` ` `int` `N = arr.length;` ` ` `N /= ` `2` `;` ` ` `System.out.println(findMinimumAdjacentSwaps(arr, N));` ` ` `}` `}` `// This code is contributed by` `// Sanjit_Prasad` |

## Python3

`# Python3 Program to find the minimum number of` `# adjacent swaps to arrange similar items together` `# Function to find minimum swaps` `def` `findMinimumAdjacentSwaps(arr, N) :` ` ` ` ` `# visited array to check if value is seen already` ` ` `visited ` `=` `[` `False` `] ` `*` `(N ` `+` `1` `)` ` ` `minimumSwaps ` `=` `0` ` ` `for` `i ` `in` `range` `(` `2` `*` `N) :` ` ` `# If the arr[i] is seen first time` ` ` `if` `(visited[arr[i]] ` `=` `=` `False` `) :` ` ` `visited[arr[i]] ` `=` `True` ` ` `# stores the number of swaps required to` ` ` `# find the correct position of current` ` ` `# element's partner` ` ` `count ` `=` `0` ` ` `for` `j ` `in` `range` `( i ` `+` `1` `, ` `2` `*` `N) :` ` ` `# Increment count only if the current` ` ` `# element has not been visited yet (if is` ` ` `# visited, means it has already been placed` ` ` `# at its correct position)` ` ` `if` `(visited[arr[j]] ` `=` `=` `False` `) :` ` ` `count ` `+` `=` `1` ` ` `# If current element's partner is found` ` ` `elif` `(arr[i] ` `=` `=` `arr[j]) :` ` ` `minimumSwaps ` `+` `=` `count` ` ` ` ` `return` `minimumSwaps` `# Driver Code` `if` `__name__ ` `=` `=` `"__main__"` `:` ` ` `arr ` `=` `[ ` `1` `, ` `2` `, ` `3` `, ` `3` `, ` `1` `, ` `2` `]` ` ` `N ` `=` `len` `(arr)` ` ` `N ` `/` `/` `=` `2` ` ` `print` `(findMinimumAdjacentSwaps(arr, N))` `# This code is contributed by Ryuga` |

## C#

`// C# Program to find the minimum` `// number of adjacent swaps to` `// arrange similar items together` `using` `System;` `class` `GFG` `{` ` ` `// Function to find minimum swaps` ` ` `static` `int` `findMinimumAdjacentSwaps(` `int` `[]arr, ` `int` `N)` ` ` `{` ` ` `// visited array to check` ` ` `// if value is seen already` ` ` `bool` `[] visited = ` `new` `bool` `[N + 1];` ` ` `int` `minimumSwaps = 0;` ` ` `for` `(` `int` `i = 0; i < 2 * N; i++)` ` ` `{` ` ` `// If the arr[i] is seen first time` ` ` `if` `(visited[arr[i]] == ` `false` `)` ` ` `{` ` ` `visited[arr[i]] = ` `true` `;` ` ` `// stores the number of swaps required to` ` ` `// find the correct position of current` ` ` `// element's partner` ` ` `int` `count = 0;` ` ` `for` `(` `int` `j = i + 1; j < 2 * N; j++)` ` ` `{` ` ` `// Increment count only if the current` ` ` `// element has not been visited yet (if is` ` ` `// visited, means it has already been placed` ` ` `// at its correct position)` ` ` `if` `(visited[arr[j]] == ` `false` `)` ` ` `count++;` ` ` `// If current element's partner is found` ` ` `else` `if` `(arr[i] == arr[j])` ` ` `minimumSwaps += count;` ` ` `}` ` ` `}` ` ` `}` ` ` `return` `minimumSwaps;` ` ` `}` ` ` `// Driver Code` ` ` `public` `static` `void` `Main(String []args)` ` ` `{` ` ` `int` `[]arr = { 1, 2, 3, 3, 1, 2 };` ` ` `int` `N = arr.Length;` ` ` `N /= 2;` ` ` `Console.WriteLine(findMinimumAdjacentSwaps(arr, N));` ` ` `}` `}` `// This code is contributed by PrinciRaj1992` |

## Javascript

`<script>` `// Javascript Program to find the minimum number of` `// adjacent swaps to arrange similar items together` `// Function to find minimum swaps` `function` `findMinimumAdjacentSwaps(arr, N)` `{` ` ` `// visited array to check if value is seen already` ` ` `let visited = Array(N + 1).fill(` `false` `);` ` ` ` ` `let minimumSwaps = 0; ` ` ` ` ` `for` `(let i = 0; i < 2 * N; i++) {` ` ` ` ` `// If the arr[i] is seen first time` ` ` `if` `(visited[arr[i]] == ` `false` `) {` ` ` `visited[arr[i]] = ` `true` `;` ` ` ` ` `// stores the number of swaps required to` ` ` `// find the correct position of current` ` ` `// element's partner` ` ` `let count = 0;` ` ` ` ` `for` `(let j = i + 1; j < 2 * N; j++) {` ` ` ` ` `// Increment count only if the current` ` ` `// element has not been visited yet (if is` ` ` `// visited, means it has already been placed` ` ` `// at its correct position)` ` ` `if` `(visited[arr[j]] == ` `false` `)` ` ` `count++;` ` ` ` ` `// If current element's partner is found` ` ` `else` `if` `(arr[i] == arr[j])` ` ` `minimumSwaps += count;` ` ` `}` ` ` `}` ` ` `}` ` ` `return` `minimumSwaps;` `}` `// driver code` ` ` `let arr = [ 1, 2, 3, 3, 1, 2 ];` ` ` `let N = arr.length;` ` ` `N = Math.floor(N / 2);` ` ` ` ` `document.write(findMinimumAdjacentSwaps(arr, N));` ` ` `</script>` |

**Output:**

5

**Time Complexity:** O(N^{2}) **Auxiliary Space: **O(N)

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**.