[Challenge]Minimum adjacent swaps required to Sort Binary array

Given a binary array, task is to sort this binary array using minimum swaps. We are allowed to swap only adjacent elements

Logic

This is more like a counting problem – we need to count the smallest number of swaps that sort the binary array. If we sort by moving all 0‘s to 1‘s left, according to the observation shown above, we can sort from right to left. Therefore the total number of swaps would be the summation of the number of 0‘s on each 1 – the number of swaps we need to move 1 to the right.

Code

ret,cnt = 0,0
j = len(arr)-1
while j >= 0:
    if arr[j] == 0:
        cnt += 1
    else:
        ret += cnt
    j -= 1

Reference

https://www.geeksforgeeks.org/minimum-swaps-required-sort-binary-array/

Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments