Search

Sort a binary array using one traversal

Given a binary array, sort it using one traversal and no extra space.


Examples :

Input : 1 0 0 1 0 1 0 1 1 1 1 1 1 0 0 1 1 0 1 0 0 
Output : 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1
Explanation: The output is a sorted array of 0 and 1

Input : 1 0 1 0 1 0 1 0 
Output : 0 0 0 0 1 1 1 1
Explanation: The output is a sorted array of 0 and 1

Solution:


void sortBinaryArray(int nums[]) 
 { 
 int j = -1; 
 for (int i = 0; i < nums.length; i++) { 
  
 // if number is smaller than 1 
 // then swap it with j-th number 
 if (a[i] < 1) { 
 j++; 
 int temp = a[j]; 
 a[j] = a[i]; 
 a[i] = temp; 
 } 
 } 
 } 





15 views0 comments

Recent Posts

See All

A string s is called good if there are no two different characters in s that have the same frequency. Given a string s, return the minimum number of characters you need to delete to make s good. The f

The numeric value of a lowercase character is defined as its position (1-indexed) in the alphabet, so the numeric value of a is 1, the numeric value of b is 2, the numeric value of c is 3, and so on.