Trusted answers to developer questions

Ravi

Given an array consisting of `0`

s, `1`

s and `2`

s, 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]`

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.

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)); } }

- 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

CONTRIBUTOR

Ravi

RELATED COURSES

View all Courses

Keep Exploring

Related Courses