Sort 0s, 1s and 2s

Given an array arr containing only 0s, 1s, and 2s. Sort the array in ascending order.

Examples:

Input: arr[]= [0, 2, 1, 2, 0]
Output: 0 0 1 2 2
Explanation: 0s 1s and 2s are segregated into ascending order.

Input: arr[] = [0, 1, 0]
Output: 0 0 1
Explanation: 0s 1s and 2s are segregated into ascending order.

Expected Time Complexity: O(n)
Expected Auxiliary Space: O(1)

Constraints:
1 <= arr.size() <= 10⁶
0 <= arr[i] <= 2

Approach 01:

#include <vector>
using namespace std;

class Solution {
public:
    void sort012(vector<int>& array) {
        int zeroCount = 0, oneCount = 0;

        // Count the occurrences of 0s and 1s
        for (int i = 0; i < array.size(); i++) {
            if (array[i] == 0) 
                zeroCount++;
            else if (array[i] == 1) 
                oneCount++;
        }

        // Refill the array with sorted values
        for (int i = 0; i < array.size(); i++) {
            if (zeroCount > 0) {
                array[i] = 0;
                zeroCount--;
            } else if (oneCount > 0) {
                array[i] = 1;
                oneCount--;
            } else {
                array[i] = 2;
            }
        }
    }
};

from typing import List

class Solution:
    def sort012(self, array: List[int]) -> None:
        zeroCount = 0
        oneCount = 0

        # Count the occurrences of 0s and 1s
        for num in array:
            if num == 0:
                zeroCount += 1
            elif num == 1:
                oneCount += 1

        # Refill the array with sorted values
        for i in range(len(array)):
            if zeroCount > 0:
                array[i] = 0
                zeroCount -= 1
            elif oneCount > 0:
                array[i] = 1
                oneCount -= 1
            else:
                array[i] = 2

Time Complexity

• Counting occurrences:

  The first for loop iterates through all elements in array, which has a size \(N\). This operation takes \(O(N)\).

• Refilling the array:

  The second for loop also iterates through all \(N\) elements of the array to overwrite them with the sorted values. This operation also takes \(O(N)\).

• Overall Time Complexity:

  The total time complexity is \(O(N)\), as both loops run sequentially.

Space Complexity

• Input array:

  The array is passed as a reference and does not contribute to additional space usage.

• Auxiliary variables:

  The function uses two integer variables, zeroCount and oneCount, along with loop counters. These require \(O(1)\) space.

• Overall Space Complexity:

  The overall space complexity is \(O(1)\), as no additional data structures are used.

Approach 02:

class Solution {
  public:
    void sort012(vector<int>& arr) {
        return sort(arr.begin(), arr.end());
    }
};

class Solution:
    def sort012(self, arr):
        arr.sort()
        return arr

Time Complexity

• Sorting Operation:

  The function sort() from the C++ Standard Library is used to sort the array arr. This function typically uses the Introsort algorithm, which has a time complexity of \( O(n \log n) \), where n is the number of elements in the array.

• Overall Time Complexity:

  The overall time complexity of the function is \( O(n \log n) \), which is dominated by the sorting operation.

Space Complexity

• In-Place Sorting:

  The sort() function performs the sorting operation in-place, meaning it does not require additional space proportional to the size of the input array. The space complexity of the sorting operation is \( O(\log n) \) due to the stack space used by the recursive calls in the Introsort algorithm.

• Overall Space Complexity:

  The overall space complexity is \( O(\log n) \), which accounts for the stack space used by the sorting algorithm.