How to sort an array of 0s, 1s, and 2s in linear time

Problem statement

Given an array consisting of 0s, 1s and 2s, sort the array.

Solve the problem in linear time.

Example 1:

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

Example 2:

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

Solution

One of the easiest solutions to this problem is to count the number of zeros, ones, and twos. Replace the elements of the array with the number of zeros, ones, and twos.

The steps of the algorithms are as follows:

  • Let the counter for the number of zeros be counter_zero.
  • Let the counter for the number of ones be counter_one.
  • Let the counter for the number of twos be counter_two.
  • Traverse the array and count the number of 0s, 1s, and 2s.
  • Traverse the array again, fill the first counter_zero elements with 0, then the next counter_one elements with 1, and finally the next counter_two elements with 2.

Time Complexity: O(n)

Space Complexity: O(1)

The downside of this approach is the array is traversed twice. Refer to The Dutch national flag problem in C++ for an optimized approach.

Code

Let’s look at the code below:

import java.util.Arrays;
class Main{
    public static void sort(int[] arr) {
        int counter_zero = 0;
        int counter_one = 0;
        int counter_two = 0;
        for(int element:arr)
            switch (element){
                case 0: counter_zero++;break;
                case 1: counter_one++;break;
                case 2: counter_two++;break;
                default:
                    System.out.println("Unknown number");
                    return;
            }
        for (int i = 0; i < counter_zero; i++)
            arr[i] = 0;
        for (int i = counter_zero; i < (counter_zero + counter_one); i++)
            arr[i] = 1;
        for (int i = (counter_zero + counter_one); i < (counter_zero + counter_one + counter_two); i++)
            arr[i] = 2;
    }
    public static void main(String[] args) {
        int[] arr = { 0, 1, 2, 0, 0, 1, 2, 1, 2};
        System.out.println("Original Array - " + Arrays.toString(arr));
        sort(arr);
        System.out.println("Sorted Array - " + Arrays.toString(arr));
    }
}

Explanation

  • Line 6: Counter for a number of zeros is defined as counter_zero.
  • Line 7: Counter for a number of ones is defined as counter_one.
  • Line 8: Counter for a number of twos is defined as counter_two.
  • Lines 10–18: The appropriate counter for each number is incremented.
  • Lines 20–21: The array is filled with zeros for counter_zero number of times.
  • Lines 23–24: The array is filled with ones for counter_one number of times.
  • Lines 26–27: The array is filled with twos for counter_two number of times.
  • Line 31: An array of 0s, 1s & 2s where arr is defined.
  • Line 33 : sort() method is called to sort arr.
Free AI Mock Interviews
Coding Interview
Coding PatternsFree Interview
Gain insights and practical experience with coding patterns through targeted MCQs and coding problems, designed to match and challenge your expertise level.
System Design
You TubeFree Interview
Learn to design a video streaming platform like YouTube by tackling functional and non-functional requirements, core components, and high-level to detailed design challenges.

Free Resources

License: Creative Commons-Attribution-ShareAlike 4.0 (CC-BY-SA 4.0)