Relative Sort Array

You are given two arrays, arr1 and arr2. The elements of arr2 are distinct, and every element of arr2 is guaranteed to appear at least once in arr1. Sort the elements of arr1 so that the relative ordering of items matches the ordering in arr2. Elements of arr1 that do not appear in arr2 should be placed at the end of the result in ascending numerical order.

Input: The first line contains n1, the size of arr1. The second line contains n1 space-separated integers (arr1). The third line contains n2, the size of arr2. The fourth line contains n2 space-separated distinct integers (arr2). Output: Print the n1 integers of arr1 rearranged: first following the relative order given by arr2, then the remaining values in ascending order, space-separated on a single line.

1 <= n1 <= 8000 1 <= n2 <= n1 0 <= arr1[i], arr2[i] <= 1000 arr2 consists of distinct values, each of which appears at least once in arr1

This is really a 'partial counting sort guided by a custom priority order' rather than a standard sort - recognizing that the reference array (arr2) essentially defines a custom bucket-processing order is the key insight.

Sort one array so its shared elements follow the exact order given by a second, reference array, with leftover elements appended in ascending order. Brute force: Sort arr1 using a custom comparator that checks each value's position in arr2 (or a large sentinel if absent) - this works but requires building an index-lookup structure and running a full comparison sort, when a counting-based approach achieves the same result more directly. Optimised: Counting arr1's values once, then simply WALKING arr2 in its given order and emitting each value the counted number of times, directly produces the correctly-ordered shared portion without any comparison-based sorting at all - only the LEFTOVER values (not in arr2) need an actual sort, and there are typically few of those.

1. Count how many times each distinct value occurs in arr1 first. 2. Walk through arr2 IN ORDER, and for each value, emit it that many times (using arr1's counts) - this fixes the relative order for all shared values. 3. Whatever values remain (not present in arr2) get appended afterward in ascending numerical order, using their leftover counts.

Time: O(n1 + n2 log n2) in the typical case - counting arr1 is O(n1), walking arr2 is O(n2), and sorting the leftover values costs O(remaining log remaining) at most. Space: O(n1), for the frequency count of arr1's values.

Every element of arr1 could belong to arr2 (no leftover tail at all), or arr1 could contain many repeated values for a single number in arr2.

Be ready to mention the counting-sort-based approach as more elegant than a custom-comparator sort here, specifically because arr1's values are bounded (0 to 1000) - a fixed-size count array makes this even more direct.