Minimum adjacent swaps required to sort Binary Array in O(n) | Amazon Interview Question

Problem

Given an array consisting of only 1s and 0s, your task is to sort this binary array such that all 0s are on the left and all 1s are on the right. You are allowed to swap only adjacent elements. Find the minimum number of swaps required to sort this array.

Input

The first line contains an integer n, the number of elements in array arr[].
The next line contains n space-separated integers arr[i].

Output

int: minimum number of swaps required to sort the input array

Sample Input

7
1 1 0 0 0 1 0

Sample Output

9

Explanation
Input array : [1, 1, 0, 0, 0, 1, 0]

1st swap : [1, 1, 0, 0, 0, 0, 1]
2nd swap : [1, 0, 1, 0, 0, 0, 1]
3rd swap : [1, 0, 0, 1, 0, 0, 1]
4th swap : [1, 0, 0, 0, 1, 0, 1]
5th swap : [1, 0, 0, 0, 0, 1, 1]
6th swap : [0, 1, 0, 0, 0, 1, 1]
7th swap : [0, 0, 1, 0, 0, 1, 1]
8th swap : [0, 0, 0, 1, 0, 1, 1]
9th swap : [0, 0, 0, 0, 1, 1, 1]

Solution

Approach: Greedy Approach

The idea is to traverse the array in reverse from the n-1th index to the 0th index and maintain a variable currOnePos (initialised as n-1), saving the current position of the sorted left-most 1. We will keep updating the variable currOnePos as we’ll encounter 1 in the array, and add the difference between the index of the encountered 1 and currOnePos to the required answer.

Code Implementation

//
//  main.cpp
//  Sort Binary Array
//
//  Created by Himanshu on 06/04/22.
//

#include <iostream>
using namespace std;

int solve (int arr[], int n) {
    int ans = 0;
    int currOnePos = n-1;
    
    for (int index=n-1; index>=0; index--) {
        if (arr[index] == 1) {
            ans += currOnePos-index;
            currOnePos--;
        }
    }

    return ans;
}

int main() {
    
    int n;
    cin>>n;
    
    int *arr = new int[n]();
    
    for (int i=0; i<n; i++) {
        cin>>arr[i];
    }
    
    cout<<solve(arr, n)<<endl;
    
    return 0;
}

Time complexity: O(n), where n is the size of array

Here’s a working example: Ideone