Loading…

easyBasicsSometimes asked

Sort 0s and 1s

Basics · 6 min

Given a binary array nums of 0s and 1s, sort it in place so all 0s come before all 1s.

In plain English

Count the zeros and rewrite, or use two pointers to swap 0s to the front.

Examples

Example 1

Input: nums = [1, 0, 1, 0]
Output: [0, 0, 1, 1]
Note: Zeros first.

Example 2

Input: nums = [0, 0]
Output: [0, 0]
Note: Already sorted.

Example 3

Input: nums = [1]
Output: [1]
Note: Single.

Constraints

1 ≤ nums.length ≤ 10^5
nums[i] ∈ {0, 1}

Clarifying questions1First question: Can I overwrite in place?Explore questions

Q1.Can I overwrite in place?
Yes — count then rewrite; otherwise I'd use two pointers.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Count the zeros, then fill that many 0s followed by 1s. O(n) time, O(1) space, single value-write pass.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you recognise counting sort for a tiny value set.

Where candidates slip

Using a comparison sort, or a boundary off-by-one.

How to stand out

Mention the two-pointer variant and the Dutch National Flag generalisation.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 1 · Optimal

Count and overwrite

TimeO(n)SpaceO(1)

This is the standard, expected solution — lead with it.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Only two values — do you actually need to compare anything?

2Hint 2Explore hint

Count the zeros, then write zeros-then-ones.

3Hint 3Explore hint

How would you extend this to 0s, 1s, and 2s?

A · Core idea

With only two distinct values, sorting reduces to counting. Count the zeros, then overwrite the array with that many 0s followed by 1s. O(n) time, O(1) space, beating any comparison sort.

Why counting beats comparison sort. Comparison sorts are bounded by O(n log n). But when the value set is tiny and known, you don't need comparisons — count occurrences and rewrite. This is counting sort specialised to two values.

The two-pointer alternative. A left/right pointer pair can swap 0s to the front in a single pass without a separate count — useful when you can't overwrite freely. Both are O(n)/O(1).

Generalises to three (Dutch flag). Sorting 0s/1s/2s in one pass is the Dutch National Flag problem — a natural follow-up worth naming.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

nums = [1, 0, 1, 0]

count

two 0s

Statezeros=2

Final result[0, 0, 1, 1]

C · Code with teaching comments

solution.javaJava

Count and overwrite — optimal

2 teaching notes

1
public void sortBinary(int[] nums) {
2
    int zeros = 0;
3
    // Count the zeros.
4
    for (int v : nums) if (v == 0) zeros++;
5
    for (int i = 0; i < nums.length; i++) {
6
        // First `zeros` slots are 0, the rest 1.
7
        nums[i] = i < zeros ? 0 : 1;
8
    }
9
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.9 lines

D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proof

ComplexityO(n) time, O(1) space — one pass to count and one to overwrite → O(n), with O(1) extra space.

E · Edge cases and pitfalls5nums = [0, 0] — Already sorted.Explore edge cases

Edge cases handled

nums = [0, 0]Already sorted.
nums = [1]Single element.
nums = [1,1,1]Zero zeros → all 1s.

Pitfalls

Reaching for a full O(n log n) sort on binary data.
Off-by-one on the zero-count boundary.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic void sortBinary(int[] nums) { int zeros = 0; for (int v : nums) if (v == 0) zeros++; for (int i = 0; i < nums.length; i++) { nums[i] = i < zeros ? 0 : 1;Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Reaching for a full O(n log n) sort on binary data.
Off-by-one on the zero-count boundary.

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Counting sort (2 values)

Code pattern to memorize

zeros=count(0); a[i]= i<zeros ? 0 : 1

Rules to remember

1Count the zeros.
2Write 0s then 1s.
3O(n), no comparisons.

Use this pattern when

Few distinct values
Counting sort

Choose another pattern when

Many distinct values — counting sort's range blows up

Interview takeaway

Few distinct values? Count and overwrite, don't comparison-sort.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternA core fresher pattern: Counting sort (2 values). Master it on small inputs and it transfers to harder problems.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Sort Colors (0s,1s,2s)
Coming soon
Dutch National Flag — three-way one-pass partition.

Same pattern

easyBasicsSometimes asked

Sort 0s and 1s

Basics · 6 min

Given a binary array nums of 0s and 1s, sort it in place so all 0s come before all 1s.

In plain English

Count the zeros and rewrite, or use two pointers to swap 0s to the front.

Examples

Example 1

Input: nums = [1, 0, 1, 0]
Output: [0, 0, 1, 1]
Note: Zeros first.

Example 2

Input: nums = [0, 0]
Output: [0, 0]
Note: Already sorted.

Example 3

Input: nums = [1]
Output: [1]
Note: Single.

Constraints

1 ≤ nums.length ≤ 10^5
nums[i] ∈ {0, 1}

Clarifying questions1First question: Can I overwrite in place?Explore questions

Q1.Can I overwrite in place?
Yes — count then rewrite; otherwise I'd use two pointers.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Count the zeros, then fill that many 0s followed by 1s. O(n) time, O(1) space, single value-write pass.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you recognise counting sort for a tiny value set.

Where candidates slip

Using a comparison sort, or a boundary off-by-one.

How to stand out

Mention the two-pointer variant and the Dutch National Flag generalisation.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 1 · Optimal

Count and overwrite

TimeO(n)SpaceO(1)

This is the standard, expected solution — lead with it.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Only two values — do you actually need to compare anything?

2Hint 2Explore hint

Count the zeros, then write zeros-then-ones.

3Hint 3Explore hint

How would you extend this to 0s, 1s, and 2s?

A · Core idea

With only two distinct values, sorting reduces to counting. Count the zeros, then overwrite the array with that many 0s followed by 1s. O(n) time, O(1) space, beating any comparison sort.

The two-pointer alternative. A left/right pointer pair can swap 0s to the front in a single pass without a separate count — useful when you can't overwrite freely. Both are O(n)/O(1).

Generalises to three (Dutch flag). Sorting 0s/1s/2s in one pass is the Dutch National Flag problem — a natural follow-up worth naming.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

nums = [1, 0, 1, 0]

count

two 0s

Statezeros=2

Final result[0, 0, 1, 1]

C · Code with teaching comments

solution.javaJava

Count and overwrite — optimal

2 teaching notes

1
public void sortBinary(int[] nums) {
2
    int zeros = 0;
3
    // Count the zeros.
4
    for (int v : nums) if (v == 0) zeros++;
5
    for (int i = 0; i < nums.length; i++) {
6
        // First `zeros` slots are 0, the rest 1.
7
        nums[i] = i < zeros ? 0 : 1;
8
    }
9
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.9 lines

D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proof

ComplexityO(n) time, O(1) space — one pass to count and one to overwrite → O(n), with O(1) extra space.

E · Edge cases and pitfalls5nums = [0, 0] — Already sorted.Explore edge cases

Edge cases handled

nums = [0, 0]Already sorted.
nums = [1]Single element.
nums = [1,1,1]Zero zeros → all 1s.

Pitfalls

Reaching for a full O(n log n) sort on binary data.
Off-by-one on the zero-count boundary.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Reaching for a full O(n log n) sort on binary data.
Off-by-one on the zero-count boundary.

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Counting sort (2 values)

Code pattern to memorize

zeros=count(0); a[i]= i<zeros ? 0 : 1

Rules to remember

1Count the zeros.
2Write 0s then 1s.
3O(n), no comparisons.

Use this pattern when

Few distinct values
Counting sort

Choose another pattern when

Many distinct values — counting sort's range blows up

Interview takeaway

Few distinct values? Count and overwrite, don't comparison-sort.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternA core fresher pattern: Counting sort (2 values). Master it on small inputs and it transfers to harder problems.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Sort Colors (0s,1s,2s)
Coming soon
Dutch National Flag — three-way one-pass partition.

Same pattern