Move 0/1 InArray

https://leetcode.com/discuss/interview-question/1655441/Amazon-or-OA

Given an array containing only 0 and 1 as its elements. We have to sort the array in such a manner that all the ones are grouped together and all the zeros are grouped together. The group of ones can be either at the start of the array or at the end of the array. The constraint while sorting is that every one/zero can be swapped only with its adjacent zero/one. Find the minimum number of moves to sort the array as per the description.

Example: input array ={0,1,0,1} Final array = {0,0,1,1} Minimum moves = 1 (1 at index 1 is swapped with 0 at index 2)

input array = { 1101} Final array - {1110} Minimum moves = 1 {1 at index 2 is swapped with index 3}

Example 3: {1,0,0,1,0,1,1,0,0,1} Minimum moves = 8

Solution:

Version 1: O(n^2)

Say we are sorting with 0s first and then 1s. So, if the element in position i is 1 then the number of swaps required is number of 0s to it's right Same for 1s first and then 0s. So we traverse from the right and get the total number of swaps for each case and return the minimum.

int minSwaps(int arr[]) {
return Math.min(getMinSwapFor(arr, 0), getMinSwapFor(arr, 1));
}

int getMinSwapFor(int arr[], int num) {
    int len = arr.length;
    int totalNumberOfSwaps = 0, currNumberOfSwaps = 0;
    for (int i = len-1; i >= 0; i--) {
        if (arr[i] == num) {
            currNumberOfSwaps++;
        } else {
            totalNumberOfSwaps += currNumberOfSwaps;
        }
    }
    return totalNumberOfSwaps;
}

https://www.geeksforgeeks.org/minimum-swaps-required-group-1s-together/ similar as LC 1151: