Relative Sort Array — Editorial

Opening the reading…

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.

The count array records what remains to be emitted.

Approach

Create 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.

Create an empty result vector, because both phases must append to one sequence whose length eventually matches arr1.

Visit 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.

Decrease the count after each append, because a consumed occurrence must not appear again during the later scan of the remaining values.

Scan 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.

Return 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

MEASURE	BOUND	WHY
Time	O(n + m + V)	Counting touches each of the n elements once. The arr2 phase examines m distinct values and emits each arr1 occurrence once overall; the final scan examines each of the V possible values and emits only the occurrences not emitted earlier. The bound does not depend on the arrangement of either array.
Space	O(V) extra	The count array has V entries, and the result vector is required output and is excluded from the extra-space bound. The extra memory therefore stays O(V), or O(1) under the fixed value limit of 0 through 1000; no input shape makes it larger.

Here n is arr1.length, m is arr2.length, and V is the number of possible values, which is 1001 for values 0 through 1000.

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

CPPCount arr1, consume arr2 groups, then emit every remaining count in value order.

#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.

CPPRank arr2 values and sort arr1 by priority first, then by numeric value.

#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;
    }
};