#include <bits/stdc++.h>
using namespace std;

// Given an array arr[] containing only 0s, 1s, and 2s. Sort the array
// in ascending order. Note: You need to solve this problem without
// utilizing the built-in sort function.
    
// Constraints:
// 1 ≤ arr.size() ≤ 10^6
// 0 ≤ arr[i] ≤ 2

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

// Follow up: Could you come up with a one-pass algorithm using only
// constant extra space?

class Solution {
  public:
    void sort012(vector<int>& arr)
    {
        // Index 0 num zeros, Index 1 num ones, Index 2 num twos
        vector<int> num012s{0,0,0};
    
        for (const auto& i: arr)
        {
            switch(i)
            {
                case 0: num012s.at(0)++; break;
                case 1: num012s.at(1)++; break;
                case 2: num012s.at(2)++; break;                
            }
        }

        // create sorted array
        int index = 0;
        for (int i = 0; i < num012s.at(0); i++) arr[index++] = 0;
        for (int i = 0; i < num012s.at(1); i++) arr[index++] = 1;
        for (int i = 0; i < num012s.at(2); i++) arr[index++] = 2;
        
        print(arr, "actual");
    }

    void print(const vector<int>& v, const string& tag)
    {
        cout << setw(12) << tag << ": ";
        for (const auto& j: v) cout << setw(3) << j << " ";
        cout << endl;
    }

    void buildPrefixSumArray(const vector<int>& arr)
    {
        vector<int> prefixSumArr{arr[0]};
        
        for (size_t i = 1; i < arr.size(); i++)
            prefixSumArr.push_back(prefixSumArr[i-1] + arr[i]);

        print(arr, "array");
        print(prefixSumArr, "prefixSum");
    }
};

int main() 
{
    vector<tuple<vector<int>, vector<int>>> v = {
        // input          expected
        { {0,1,2,0,1,2}, {0,0,1,1,2,2} },
    };

    Solution s;

    s.buildPrefixSumArray(get<0>(v.at(0)));
    
    for (auto i: v)
    {
        s.print(get<0>(i), "input");
        s.print(get<1>(i), "expected");

        s.sort012(get<0>(i));
    }
    
    return 0;
}