Sort 0 and 1 Problem Statement

Given an integer array ARR of size N containing only integers 0 and 1, implement a function to sort this array. The solution should scan the array only once without using any additional arrays.

Input:

The first line contains an integer 't', denoting the number of test cases or queries to be run. The next t lines contain: - An integer 'N' representing the size of the array/list in each test case. - 'N' single space-separated integers (all 0s and 1s) representing the elements in the array.

Output:

For each test case, print the sorted array elements in one row, separated by a single space. Output for every test case will be printed on a separate line.

Example:

Input:

2 5 0 1 1 0 1 3 1 0 0

Output:

0 0 1 1 1 0 0 1

Constraints:

1

Question

Sort 0 and 1 Problem Statement

Given an integer array ARR of size N containing only integers 0 and 1, implement a function to sort this array. The solution should scan the array only once without using any additional arrays.

Input:

The first line contains an integer 't', denoting the number of test cases or queries to be run. 
The next t lines contain: 
- An integer 'N' representing the size of the array/list in each test case. 
- 'N' single space-separated integers (all 0s and 1s) representing the elements in the array.

Output:

For each test case, print the sorted array elements in one row, separated by a single space. 
Output for every test case will be printed on a separate line.

Example:

Input:

Output:

0 0 1 1 1
0 0 1

Constraints:

1 <= t <= 10^2
0 <= N <= 10^5
Time Limit: 1 sec

Note:

You need to modify the given array/list itself. No need to return or print anything within the function.

Accepted Answer

The function sorts an integer array containing only 0s and 1s in linear time complexity.

Use two pointers, one starting from the beginning and the other from the end of the array.
Swap the elements at the pointers if the element at the beginning pointer is 1 and the element at the end pointer is 0.
Continue moving the pointers towards each other until they meet in the middle of the array.

Accepted Answer

public static int[] sortArray(int[] array) {
        for (int i = 0, j = array.length - 1 ; i < j ;) {
            if (array[i] == 1 && array[j] == 0) {
                int temp = array[i];
                array[i] = array[j];
                array[j] = temp;
                i++;
                j--;
            }
            else if (array[i] == 1 && array[j] == 1) {
                j--;
            } else if (array[i] == 0 && array[j] == 0) {
                i++;
            } else {
                j--;
                i++;
            }
        }

return array;
    }

Accepted Answer

public static int[] sort(int[] arr){
        int j=0;
        for(int i=0; i<arr.length; i++){
            if(arr[i]==0){
                swap(arr, i, j);
                j++;
            }
            System.out.println(Arrays.toString(arr));
        }
        return arr;
    }

private static void swap(int[] arr, int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

Accepted Answer

def sort_zeros_and_ones(arr):
    """
    Sorts an array containing only 0s and 1s in-place.

Args:
        arr: The input array of 0s and 1s.

Returns:
        None. The array is modified in-place.
    """
    count_zeros = arr.count(0)
    for i in range(count_zeros):
        arr[i] = 0
    for i in range(count_zeros, len(arr)):
        arr[i] = 1

# Example usage:
arr = [1, 0, 1, 0, 1, 0]
sort_zeros_and_ones(arr)
print(arr) # Output: [0, 0, 0, 0, 1, 1]

Accepted Answer

package Arrays;

public class Sort_0_and_1 {

public static void sort(int[] nums){
        int i =0,j=0;
        while(j&lt;nums.length){
            if(nums[j]==0){
                int temp = nums[j];
                nums[j]=nums[i];
                nums[i]=temp;
                i++;
            }
            j++;
        }
    }
    public static void main(String[] args) {
        int nums[] = {1,0,0,1,0,1,1,1,0};
        sort(nums);
        for(int i:nums){
            System.out.print(i+" ");
        }
    }
}

Asked in Deloitte