Minimum number of adjacent swaps of binary array

Question

Given a binary array, find the number of minimum adjacent swaps needed to group 1's and 0's.

Example:

Input : 0,1,0,1 (array with 0 based index)
Swaps needed : 0,1,0,1 -> 0,0,1,1 (1 swap from index 1 to index 2)

Solution : 1

Exmaple:

Input : 1,0,1,0,0,0,0,1
Swaps needed : 
1,0,1,0,0,0,0,1 -> 1,1,0,0,0,0,0,1 -> 1,1,0,0,0,0,1,0 -> 1,1,0,0,0,1,0,0 -> 1,1,0,0,1,0,0,0 -> 1,1,0,1,0,0,0,0 -> 1,1,1,0,0,0,0,0

Total 6 swaps so the solution is 6.

The 1's and 0's can be positioned at the beginning or end but they should be at a single place i.e. either begin or end.

I have come up with below logic for this requirement. I tried this in a hackerrank, it failed for a single hidden test case and gave timeout for 3 test cases as I have nested loops in my code.

static int countSwaps(List<Integer> list) {
    int temp;
    int swaps = 0;
    int n = list.size();
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n - 1; j++) {
            if ((list.get(j) == 0) && (list.get(j + 1) == 1)) {
                temp = list.get(j);
                list.set(j, list.get(j + 1));
                list.set(j + 1, temp);
                swaps++;
            }
        }
    }

    return swaps;
}

What is a better approach to solving this program?

I have already gone through this post Given an array of 0 and 1, find minimum no. of swaps to bring all 1s together (only adjacent swaps allowed) but the answers are not giving correct output.

The reason it's timing out is because you're actually doing the swap operations manually, which is O(n^2). There's a mathematical way to count the number of swaps without actually performing the operation. Unfortunately, off the top of my head I don't know the function, but this solves it. Instead of a O(n^2), this is an O(2n) -> O(n). — Compass
– Compass, Commented Jul 3, 2019 at 23:07
@Compass, I see that the link is for Sort Binary array, so it always tries to place 0 at first place. But in my case, the first place can be occupied by 0 or 1 — Learner
– Learner, Commented Jul 3, 2019 at 23:22
There's a way to determine which way to sort, but you could also do both sorts at O(4n) -> O(n) and take the lower value as well until you figure out that formula. Pretty sure it's just counting which side has more #s to move. — Compass
– Compass, Commented Jul 4, 2019 at 0:27

Andreas · Accepted Answer · 2019-07-04 00:04:37Z

21

Building on answer by Gene, fixing the compile error and supporting moving 1's to the left (to the beginning) or moving them to the right (to the end), aka moving 0's to the left:

static int countSwaps(int... a) {
    int n0 = 0, i0 = 0, n1 = 0, i1 = 0;
    for (int p = 0; p < a.length; ++p) {
        if (a[p] == 0)
            n0 += p - i0++; // No. of steps to move the 0 to the left
        else
            n1 += p - i1++; // No. of steps to move the 1 to the left
    }
    return Math.min(n0, n1); // Choose lowest no. of steps
}

Test

System.out.println(countSwaps(0,1,0,1));
System.out.println(countSwaps(1,0,1,0,0,0,0,1));
System.out.println(countSwaps(1,0,0,0,0,1,0,1));

Output

1
6
6

answered Jul 4, 2019 at 0:04

Andreas

160k13 gold badges164 silver badges262 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Gene · Accepted Answer · 2019-07-04 06:30:24Z

7

To move all 1's to the left, let p(i) be the position of i'th 1 from left to right. It ultimately needs to move to position i. This will need p(i) - i swaps. Just sum up this quantity for all i.

int countSwaps(int [] a) {
  int n = 0, i = 0;
  for (int p = 0; p < a.length; ++p)
    if (a[p] == 1) {
      n += p - i;
      ++i;
    }
  return n;
}

Moving to the right is symmetric. Do a similar computation and take the min.

edited Jul 4, 2019 at 6:30

answered Jul 3, 2019 at 23:37

Gene

47.1k4 gold badges64 silver badges101 bronze badges

5 Comments

Learner Over a year ago

Thanks, I am not able to understand the explanation provided, can you please explain how this logic works?

Andreas Over a year ago

That is great, except it doesn't compile.

Andreas Over a year ago

That is great, but only half the challenge. "The 1's and 0's can be positioned at the beginning or end" E.g. input 1,0,1,0,0,0,0,1 returns 6, but input 1,0,0,0,0,1,0,1 returns 9, while the real answer is also 6, since you just move the 1's right instead of left for a valid result.

Learner Over a year ago

@Gene, Based on my understanding, this logic is placing 1's at the beginning all the time, but in my case they can be kept at the end also.

Gene Over a year ago

@learner Sorry I missed the bit about beginning or end. Same idea applies. Just compute both and take the min as Andreas has.

Rainfall · Accepted Answer · 2021-11-15 15:40:22Z

1

Here is my solution (Java):

public static int minSwaps(int[] arr) {
    int min_swaps1 = 0;
    int zero_counts = 0;
    int min_swaps2 = 0;
    int one_counts = 0;

    for (int j : arr) {
        if (j == 0) {
            zero_counts++;
            min_swaps2 += one_counts;
        } else {
            one_counts++;
            min_swaps1 += zero_counts;
        }
    }

    return Math.min(min_swaps1, min_swaps2);
}

edited Nov 15, 2021 at 15:40

answered Nov 15, 2021 at 15:09

Rainfall

936 bronze badges

1 Comment

pzaenger Over a year ago

The question is about Java, not Python.

Collectives™ on Stack Overflow

Minimum number of adjacent swaps of binary array

3 Answers 3

Comments

5 Comments

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

5 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related