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 <= 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.
AnswerBot
4d
Sort an array of 0s and 1s in linear time without using additional arrays.
Use two pointers approach to swap 0s to the left and 1s to the right.
Keep track of the leftmost index of 1s to place 0s before...read more
Help your peers!
Add answer anonymously...
Top upGrad SDE-2 interview questions & answers
Popular interview questions of SDE-2
Stay ahead in your career. Get AmbitionBox app
Helping over 1 Crore job seekers every month in choosing their right fit company
65 L+
Reviews
4 L+
Interviews
4 Cr+
Salaries
1 Cr+
Users/Month
Contribute to help millions
Get AmbitionBox app