Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

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

Ravi

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.

RELATED TAGS

RELATED COURSES

View all Courses

Keep Exploring