Relative Sort Array

Intuitionthe output is a controlled spending order for each value's frequency

The result has two independent parts. First, every occurrence of a value named in arr2 must appear together, and the groups must follow arr2 from left to right. Second, every value not named in arr2 belongs after those groups, where ordinary ascending order decides its position. The original positions in arr1 do not matter once you know how many times each value occurs.

Count arr1 first. When you visit a value in arr2, emit its entire remaining count immediately, so duplicates stay together and the order of arr2 controls the groups. After that, scan values from smallest to largest and emit whatever counts remain. Values already emitted have no count left, while values absent from arr2 still have their counts, so this one scan creates exactly the required suffix.

Approach

1. 1Create a count array covering every possible value and count each element of arr1, because storing only one occurrence would lose the multiplicity required in the answer.
2. 2Create an empty result vector, because both phases must append to one sequence whose length eventually matches arr1.
3. 3Visit arr2 from left to right and repeatedly append the current value while its count is positive, because one append per distinct arr2 value would omit duplicates.
4. 4Decrease the count after each append, because a consumed occurrence must not appear again during the later scan of the remaining values.
5. 5Scan the entire value range in increasing order and append each value while its remaining count is positive, because this places every value absent from arr2 in ascending order and skips values already consumed.
6. 6Return the result after both phases, because arr2 accounts for its values and the range scan accounts for every leftover occurrence.

Complexitythe value range is bounded independently of the input order

Annotated solutionC++ · counting sort · one frequency table and two emission phases

#include <vector>
using namespace std;

class Solution {
public:
    vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) {
        vector<int> count(1001, 0);
        for (int value : arr1) {
            count[value]++;
        }

        vector<int> result;
        for (int value : arr2) {
            while (count[value] > 0) {
                result.push_back(value);
                count[value]--;
            }
        }

        for (int value = 0; value <= 1000; value++) {
            while (count[value] > 0) {
                result.push_back(value);
                count[value]--;
            }
        }

        return result;
    }
};

The key placement is the count decrement. The arr2 loop does not merely identify which values have priority; it consumes all occurrences of each priority value. That leaves a zero count behind, so the final scan cannot duplicate them. The second loop is deliberately over numeric values rather than over arr1, because numeric iteration is what supplies ascending order for elements absent from arr2.

The comparator alternativea reasonable general-purpose version when the value range is not small

You can also assign each arr2 value a rank and sort arr1 with a comparator. A ranked value comes before an unranked value; two ranked values compare by their arr2 ranks; two unranked values compare numerically. This is a different arrangement, not an optimisation here: it uses O(n log n) time and O(m) extra rank storage, while counting is linear because the value range is small and known.

#include <algorithm>
#include <unordered_map>
#include <vector>
using namespace std;

class Solution {
public:
    vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) {
        unordered_map<int, int> rank;
        for (int i = 0; i < static_cast<int>(arr2.size()); i++) {
            rank[arr2[i]] = i;
        }

        sort(arr1.begin(), arr1.end(), [&](int a, int b) {
            bool aInArr2 = rank.count(a) > 0;
            bool bInArr2 = rank.count(b) > 0;

            if (aInArr2 && bInArr2) {
                return rank[a] < rank[b];
            }
            if (aInArr2 != bInArr2) {
                return aInArr2;
            }
            return a < b;
        });

        return arr1;
    }
};

Common mistakestwo lines that quietly change the required ordering