Skip to main content

Sort Colors

Problem​

Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue.

We will use the integers 0, 1, and 2 to represent the color red, white, and blue, respectively.

You must solve this problem without using the library's sort function.

Solution Approach​

Expected Time complexity: O(n2)O(n^2)

Click - to see solution code
class Solution {
   public:
    void sortColors(vector<int>& arr) {
        int a[] = {0, 0, 0};
        int n = arr.size();
        for (int i = 0; i < n; i++) a[arr[i]]++;
        int j = 0;
        for (int i = 0; i < 3; i++) {
            for (int k = 0; k < a[i]; k++) arr[j++] = i;
        }
    }
};