CODEWITHSUNDEEP
algorithmdata-structures
user13713231
user13713231

Reputation:

What is the minimum number of adjacent swaps needed to segregate a list of 0s and 1s?

I am trying to solve a Data Structures and Algorithms problem, which states that given a group of 1s and 0s, group the digits such that all 0s are together and all 1s are together. What is the minimum number of swaps required to accomplish this if one can only swap two adjacent elements? It does not matter which group is at what end.

Eg:

[0,1,0,1] = [0,0,1,1] 1 swaps

[1,1,1,1,0,1,0] = [1,1,1,1,1,0,0] 1 swaps

[1, 0, 1, 0, 0, 0, 0, 1] = = [1,1,1,0,0,0,0,0] 6 swaps

Note that this is different from the questions asked here:

Find the minimum number of swaps required such that all the 0s and all the 1s are together

I am not sorting the array, I am just trying to group all the 0s and all the 1s together and it does not matter which is at which end.

I really have no clue where to even start. Can someone help me?

Upvotes: 2

Views: 6993

Answers (3)

Dave
Dave

Reputation: 9075

Let's focus on zeroes. Each swap moves a single zero a single position closer to the final order. Then we can find the number of swaps by finding the number of displaced zeroes, and the severity of the displacement.

Let's start by assuming that the zeroes end up at the start of the array. We'll keep track of two things: count_of_ones, and displacement, both initialized to zero. Each time we find a 1, we increment count_of_ones. Each time we find a 0, we increase displacement by count_of_ones.

Then we do this in the other direction. Both ways are linear, so this is linear.

E.g. 1010001

1: count_of_ones: 0 -> 1
0: displacement: 0 -> 1
1: count_of_ones: 1 -> 2
0: displacement: 1 -> 3
0: displacement: 3 -> 5
0: displacement: 5 -> 7
1: count_of_ones: 2 -> 3

The answer for this direction is the final displacement, or 7. Going the other way we get 5. Final answer is 5.

In fact, the sum of the final displacements (starting vs ending with all zeroes) will always equal num_zeroes * num_ones. This halves the work (though it's still linear).

From the comments it seems some people didn't understand my answer. Here's a Ruby implementation to make things clearer.

def find_min_swaps(arr)
  count_of_ones = 0
  displacement = 0
  arr.each do |v|
    count_of_ones += 1 if v == 1
    displacement += count_of_ones if v == 0
  end

  count_of_zeroes = arr.length - count_of_ones
  reverse_displacement = count_of_ones * count_of_zeroes - displacement
  return [displacement, reverse_displacement].min
end

The zeroes end up on the left if displacement < reverse_displacement, either if they're equal, or the right if displacement > reverse_displacement.

Upvotes: 5

Giorgi Tsiklauri
Giorgi Tsiklauri

Reputation: 11120

Simple approach using Bubble Sort, which takes O(n2), would be this:

public class MainClass {

    public static void main(String[] args) {
        int[] arr = new int[]{1, 0, 0, 0, 0, 0, 0, 1, 0};
        int minSwaps = minimumSwaps(arr);
        System.out.println("Minimum swaps required: " + minSwaps);
    }

    public static int minimumSwaps(int[] array) {
        int[] arr1 = array.clone(), arr2 = array.clone();
        int swapsForRight = 0, swapsForLeft = 0;

        boolean sorted = false;

        while (!sorted) {
            sorted = true;
            for (int i = 0; i < arr1.length - 1; i++) {
                if (arr1[i + 1] < arr1[i]) {
                    int temp = arr1[i + 1];
                    arr1[i + 1] = arr1[i];
                    arr1[i] = temp;
                    sorted = false;
                    swapsForRight++;
                }
            }
        }
            
        sorted = false;
        while (!sorted) {
            sorted = true;
            for (int i = 0; i > arr2.length - 1; i++) {
                if (arr2[i + 1] < arr2[i]) {
                    int temp = arr2[i + 1];
                    arr2[i + 1] = arr2[i];
                    arr2[i] = temp;
                    sorted = false;
                    swapsForLeft++;
                }
            }
        }
        return swapsForLeft > swapsForRight ? swapsForRight : swapsForLeft;
    }
}

Upvotes: 0

Matt Timmermans
Matt Timmermans

Reputation: 59154

Let SUM0 be the sum of the (0-based) indexes of all the zeros, and let SUM1 be the sum of the indexes of all the ones. Every time you swap 10 -> 01, SUM0 goes down by one, and SUM1 goes up by one. They go the other way when you swap 01 -> 10.

Lets say you have N0 zeros and N1 ones. If the zeros were packed together at the start of the array, then you would have SUM0 = N0*(N0-1)/2. That's the smallest SUM0 you can have.

Since a single adjacent swap can reduce SUM0 by exactly one, it takes exactly SUM0 - N0*(N0-1)/2 swaps to pack the zeros together at the front. Similarly, it takes SUM1 - N1*(N1-1)/2 swaps to pack the ones together at the front.

Your answer is the smaller of these numbers: min( SUM0 - N0*(N0-1)/2 , SUM1 - N1*(N1-1)/2 )

Those values are all easy to calculate in linear time.

Upvotes: 1

Related Questions