Minimum swaps to place even numbers at even indices

Given an array Arr[N] of integers, where N is the size of the array. Our task is to rearrange the array such that arr[i]%2 = i%2, in other words, the element at even index must be even and odd at odd index in the array. The task should be completed in a minimum number of swaps.

Examples :

Input Array[]= {12, 6, 9, 4, 81, 3}
Output array[]= {12, 9, 6, 81, 4, 3}
Number of swaps = 2
First swap (6, 9) and second swap (4, 81).

Input Array[]= {1, 9, 4, 11, 16, 10}
Output array[]= {10, 9, 4, 11, 16, 1}
Number of swaps = 1
Swap (1, 10)

Naive Approach :

Using nested for loops. Outer loop traverses the array and inner loop checks the right side of the every index. If current index element (arr[i]) does not satisfy the condition (arr[i]%2 == i%2) then inner loop iterates the array on its right side and finds the proper fit for swapping with current element. The counter increases every time there is a swap.

Time Complexity : O(N*N)
Space Complexity : O(1)

Efficient Approach :

Using a double ended queue. Insert index of those elements which are even but the index is odd in the left end of the queue. Similarly, insert index of those elements which are odd but the index is even in the right end of the queue. Now, pop the queue from left and right end and swap the elements corresponding to those index in the array.

Time Complexity : O(N)
Space Complexity : O(N)

//Program to rearrange the input array.
// such that arr[i]%2 = i%2.

#include <iostream>
#include <deque>
using namespace std;

//Utility function
void MinimumSwaps(int arr[], int n)
{
  deque <int> dq;
  for(int i=0; i<n; i++)
  {
    if(arr[i]%2==i%2)
      continue;
    else if(arr[i]%2==0)
      dq.push_front(i);
    else
      dq.push_back(i);
  }
  
  int even,odd,temp,count=0;
  while(!dq.empty())
  {
    even=dq.front();
    dq.pop_front();
    odd=dq.back();
    dq.pop_back();
    
    temp=arr[even];
    arr[even]=arr[odd];
    arr[odd]=temp;
    count+=1;
  }
  
  cout<<"\nMin swaps => "<<count<<endl;
}

//Display function.
void Display(int arr[], int n)
{
    for(int i=0; i<n; i++)
    cout<<arr[i]<<" ";
    cout<<endl;
}

//Main function.
int main() {

   int arr[]={12, 6, 9, 4, 81, 3};
   int n=sizeof(arr)/sizeof(int);
  
   cout<<"Input array=> \n";
   Display(arr,n);
   MinimumSwaps(arr,n);
   cout<<"\nOutput array=> \n";
   Display(arr,n);
   return 0;
}

Input array=> 
12 6 9 4 81 3 

Min swaps => 2

Output array=> 
12 9 6 81 4 3

Time Complexity : O(N)

Space Complexity : O(N)