Three Number Sort

• Time : O(n)
• Space : O(1)

c++

vector<int> threeNumberSort(vector<int> array, vector<int> order) {
    int n = array.size(), l = 0;
    for(int i = 0; i < n; i++) {
        if(array[i] == order[0])
            swap(array[l++], array[i]);
    }
    for(int i = l; i < n; i++) {
        if(array[i] == order[1])
            swap(array[l++], array[i]);
    }
    return array;
}

• Time : O(n)
• Space : O(1)

c++

vector<int> threeNumberSort(vector<int> array, vector<int> order) {
    int n = array.size(), l = 0, r = n - 1;
    while(l < r and array[l] == order[0]) l++;
    while(l < r and array[r] == order[2]) r--;
    for(int i = l; i <= r and l < r; i++) {
        if(array[i] == order[0]) {
            swap(array[l++], array[i]);
        } else if(array[i] == order[2]) {
            swap(array[r--], array[i--]);
        }
    }
    return array;
}