Articles

Blogs

MCQ

SQL

Q&A

Tools

Tags

Jobs

News

Community

LogIn

Email

Password

Show Password

Forget Password

I don't have account.Sign Up!

Login

‹ ›

‹ ›

‹ ›

‹ ›

Sponsored -53%

Zebronics #1 Best Seller

ZEBRONICS Blanc Slim Wireless Mouse — Rechargeable, BT + 2.4GHz (Black)

Up to 1600 DPI · Silent clicks · 63g · Multicolor LED

★★★★★★★★★★ 4.0 (9,512) 5K+ bought last month

₹376 M.R.P. ₹799Save ₹423

Buy Now →

Adℹ

✕

Sort an Array of 0s and 1s

HackFury

Last Updated : 05 October 2025

15 Views

#array

#sorting

#coding-problems

#two-pointers

Adℹ

Given an array consisting of only 0s and 1s, sort the array in ascending order (all 0s first, followed by all 1s). The sorting must be done in-place without using built-in sort.

Example 1

Input: arr = [0, 1, 1, 0, 1, 0, 0, 1]
Output: [0, 0, 0, 0, 1, 1, 1, 1]

Example 2

Input: arr = [1, 1, 1, 0, 0, 0]
Output: [0, 0, 0, 1, 1, 1]

Constraints

• 1 <= arr.length <= 10^6

• arr[i] ∈ {0,1}

Counting Method (Linear Time)

Idea We can simply count how many 0s (and 1s) exist in the array. Once we know that:

• The first count0 positions should be filled with 0s

• The rest should be filled with 1s

That's it, the array becomes sorted!

//---------------Java---------------------
public static void sortCounting(int[] arr) {
    int count0 = 0;
    for (int num : arr) {
        if (num == 0) count0++;
    }
    for (int i = 0; i < count0; i++) {
        arr[i] = 0;
    }
    for (int i = count0; i < arr.length; i++) {
        arr[i] = 1;
    }
}

Complexity Analysis

• Time Complexity: O(n), Single pass to count + another to overwrite
• Space Complexity: O(1), Sorting done in-place

Optimal Approach: Two-Pointer Swap (Single Pass)

we'll solve this problem in a single traversal, without counting, without extra passes and without using any extra space.

This technique is called the Two-Pointer Swap Approach, a pattern used widely in high-performance systems, competitive programming and algorithmic interviews.

Core Idea

We maintain two pointers:

• left : starts from the beginning of the array

• right : starts from the end of the array

The idea is simple:

• If the element at left is already 0, it’s in the correct position -> move left forward.

• If the element at left is 1, it should go to the end -> swap it with arr[right] and move right backward.

This process continues until left < right.

The array gradually gets partitioned into two regions, all 0s on the left and all 1s on the right similar to the partition step of QuickSort.

Step-by-Step Example

Let's dry-run this with a real example:

arr = [1, 0, 1, 0, 0, 1]

Step	left	right	Action	Array State
1	0	5	arr[left] = 1 -> swap with arr[right]	[1, 0, 1, 0, 0, 1] -> [1, 0, 1, 0, 0, 1] (same since right also 1)
2	0	4	arr[left] = 1 -> swap with arr[right]	[0, 0, 1, 0, 1, 1]
3	1	3	arr[left] = 0 -> left++	[0, 0, 1, 0, 1, 1]
4	2	3	arr[left] = 1 -> swap with arr[right]	[0, 0, 0, 1, 1, 1]
Done	left >= right			Sorted array: [0, 0, 0, 1, 1, 1]

//-----------------Java-----------------
public static void sortTwoPointer(int[] arr) {
    int left = 0, right = arr.length - 1;
    while (left < right) {
        if (arr[left] == 0) {
            left++;
        } else {
            int temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
            right--;
        }
    }
}

Complexity Analysis

• Time Complexity: O(n), Each element is checked once
• Space Complexity: O(1), Sorting is done in-place

Complexity Comparison of All Approaches

Approach	Time Complexity	Space Complexity	Passes
Counting Approach	O(n)	O(1)	2
Two-Pointer (Optimal)	O(n)	O(1)	1

Trending Developer Reads

System Design Deep Dive: 25 Essential Interview Questions

Rippling SDE-2 Interview Experience (4+ Years Experience) | Offer Received | Coding, LLD & System Design

Top 50 SQL Interview Questions and Answers (Beginner to Intermediate)

Meesho SDE-1 Online Assessment Interview Experience (Remote) - Rejected

DSA Patterns for Coding Interviews: Complete LeetCode Roadmap (Beginner to Advanced)

Spinny SDE-1 Interview Experience (Selected)

Top 50+ SQL Interview Questions and Answers for Intermediate to Advanced

Google L4 Software Engineer III interview experience | Selected

Amazon SDE-2 Interview Experience (3 Years Experience)

Meesho SDE-1 Backend Interview Experience (Remote | 3 Round) - Rejected

Responses (0)

Write a response

Hide Comments

No Comments yet.

‹ ›

‹ ›

‹ ›

‹ ›

Sponsored -53%

Zebronics #1 Best Seller

ZEBRONICS Blanc Slim Wireless Mouse — Rechargeable, BT + 2.4GHz (Black)

Up to 1600 DPI · Silent clicks · 63g · Multicolor LED

★★★★★★★★★★ 4.0 (9,512) 5K+ bought last month

₹376 M.R.P. ₹799Save ₹423

Buy Now →

‹ ›

‹ ›

‹ ›

‹ ›

Sponsored -34%

iQOO Amazon's Choice

iQOO Z10 Lite 5G — Cyber Green, 4GB RAM, 128GB Storage

Dimensity 6300 · 50MP Sony AI Camera · 6000 mAh · IP64

★★★★★★★★★★ 4.0 (2,052) 500+ bought last month

₹18,997 M.R.P. ₹28,999Save ₹10,002

Buy Now →

\n \n \n \n \n

Given an array consisting of only 0s and 1s, sort the array in ascending order (all 0s first, followed by all 1s).\nThe sorting must be done in-place without using built-in sort.

Example 1

\nInput: arr = [0, 1, 1, 0, 1, 0, 0, 1]\nOutput: [0, 0, 0, 0, 1, 1, 1, 1]\n

Example 2

\nInput: arr = [1, 1, 1, 0, 0, 0]\nOutput: [0, 0, 0, 1, 1, 1]\n

Constraints

\n
• \n

  1 <= arr.length <= 10^6

  \n
\n
• \n

  arr[i] ∈ {0,1}

  \n
\n

Counting Method (Linear Time)

Idea\nWe can simply count how many 0s (and 1s) exist in the array.\nOnce we know that:

\n
• \n

  The first count0 positions should be filled with 0s

  \n
\n
• \n

  The rest should be filled with 1s

  \n
\n

That's it, the array becomes sorted!

//---------------Java---------------------\npublic static void sortCounting(int[] arr) {\n    int count0 = 0;\n    for (int num : arr) {\n        if (num == 0) count0++;\n    }\n    for (int i = 0; i < count0; i++) {\n        arr[i] = 0;\n    }\n    for (int i = count0; i < arr.length; i++) {\n        arr[i] = 1;\n    }\n}\n

Complexity Analysis

\n
• Time Complexity:\tO(n),\tSingle pass to count + another to overwrite
\n
• Space Complexity:\tO(1),\tSorting done in-place
\n

Optimal Approach: Two-Pointer Swap (Single Pass)

we'll solve this problem in a single traversal, without counting, without extra passes and without using any extra space.

This technique is called the Two-Pointer Swap Approach, a pattern used widely in high-performance systems, competitive programming\nand algorithmic interviews.

Core Idea

We maintain two pointers:

\n
• \n

  left : starts from the beginning of the array

  \n
\n
• \n

  right : starts from the end of the array

  \n
\n

The idea is simple:

\n
• \n

  If the element at left is already 0, it’s in the correct position -> move left forward.

  \n
\n
• \n

  If the element at left is 1, it should go to the end -> swap it with arr[right] and move right backward.

  \n
\n

This process continues until left < right.

The array gradually gets partitioned into two regions, all 0s on the left and all 1s on the right similar to the partition step of QuickSort.

Step-by-Step Example

Let's dry-run this with a real example:

arr = [1, 0, 1, 0, 0, 1]\n

//-----------------Java-----------------\npublic static void sortTwoPointer(int[] arr) {\n    int left = 0, right = arr.length - 1;\n    while (left < right) {\n        if (arr[left] == 0) {\n            left++;\n        } else {\n            int temp = arr[left];\n            arr[left] = arr[right];\n            arr[right] = temp;\n            right--;\n        }\n    }\n}\n

Complexity Analysis

\n
• Time Complexity:\tO(n),\tEach element is checked once
\n
• Space Complexity:\tO(1),\tSorting is done in-place
\n

Complexity Comparison of All Approaches