Sort an Array of 0s, 1s, and 2s | Coding Interview | Arrays

Being easy this question has been asked by a lot of companies like Amazon, Adobe, Sap Labs, Walmart …

This problem is part of the 30 days preparation plan for coding interviews.

Description

We have an array of size N where each element is 0, 1 or 2. Sort the array in ascending order.

Input: [ 1 2 0 1 1 0 2 0 ]
n = 8:
Output: [ 0 0 0 1 1 1 2 2 ]

This problem may be asked in many forms, like the Dutch national flag problem or color sorting problem.

Approach 1: Brute Force

A brute force solution is to sort the array in-place using something like heap sort or quicksort in ascending order and we will get the sorted array.

Time and Space Complexity

Since we are using sorting the time complexity will be O(nlogn) and space complexity will be in O(1) as we are doing an in-place sorting.