Relative Sort Array

1. Define the problem

You are given two integer arrays arr1 and arr2 . The elements of arr2 are distinct, and every element of arr2 also appears in arr1 . Sort the elements of arr1 so that the relative ordering of items in arr1 matches the ordering in arr2. Elements that don't appear in arr2 go at the end, sorted in ascending order. Because every value is small and bounded, tally each value into a count array first, then read the counts off in arr2 's order, followed by whatever is left, from smallest value to largest.

Constraints

1 ≤ arr1.length, arr2.length ≤ 1000
0 ≤ arr1_i, arr2_i ≤ 1000
All the elements of arr2 are distinct
Each arr2_i is in arr1

Example

Inputarr1 = [2, 3, 1, 3, 2, 4, 6, 7, 9, 2, 19], arr2 = [2, 1, 4, 3, 9, 6]

Output[2, 2, 2, 1, 4, 3, 3, 9, 6, 7, 19]

Explanation Values that appear in arr2 come first, in arr2's order, repeated by how many times they showed up in arr1. Values not in arr2 (7 and 19) follow, sorted ascending.

2. Know the words first

In plain terms

Count array: An array indexed by value that tallies how many times each value showed up in arr1.

3. Visualize the solution

Count every value, then read it back in arr2's order

Statusinit

arr1=[2, 2, 1, 3, 3]. Count how many times each value appears.

What happens in this step

arr1 = [2, 2, 1, 3, 3]

counts[1] = 0, counts[2] = 0, counts[3] = 0  (all start at 0)

Tally each value in arr1 into a count array indexed by value.

Step 1 of 5

Steps to visualize

Tally how many times each value in arr1 occurs into a count array.
Walk arr2 in order; for each value, write it out as many times as its count says.
Walk the remaining values from smallest to largest, writing out whatever is left.
The result respects arr2's ordering first, then ascending order for the rest.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Count every value, then read it back in arr2's order

Statusinit

arr1=[2, 2, 1, 3, 3]. Count how many times each value appears.

What happens in this step

arr1 = [2, 2, 1, 3, 3]

counts[1] = 0, counts[2] = 0, counts[3] = 0  (all start at 0)

Tally each value in arr1 into a count array indexed by value.

Step 1 of 5

5. Solution

Solution

solution.tsTypeScript

function relativeSortArray(arr1, arr2) {
  const maxValue = 1000;
  const counts = new Array(maxValue + 1).fill(0);

  for (const num of arr1) {
    counts[num]++;
  }

  const result = [];

  for (const num of arr2) {
    while (counts[num] > 0) {
      result.push(num);
      counts[num]--;
    }
  }

  for (let value = 0; value <= maxValue; value++) {
    while (counts[value] > 0) {
      result.push(value);
      counts[value]--;
    }
  }

  return result;
}

Time: O(n + k)
Space: O(n + k)

6. Test cases

Test cases

Input	Expected	Covers
`arr1 = [2, 3, 1, 3, 2, 4, 6, 7, 9, 2, 19], arr2 = [2, 1, 4, 3, 9, 6]`	`[2, 2, 2, 1, 4, 3, 3, 9, 6, 7, 19]`	example from the docstring
`arr1 = [28, 6, 22, 8, 44, 17], arr2 = [22, 28, 8, 6]`	`[22, 28, 8, 6, 17, 44]`	multiple values not present in arr2, sorted ascending at the end
`arr1 = [5], arr2 = [5]`	`[5]`	smallest valid input, a single matching element
`arr1 = [10, 10, 2, 2, 5, 5, 1, 1], arr2 = [5, 1]`	`[5, 5, 1, 1, 2, 2, 10, 10]`	duplicate values on both sides of the split
`arr1 = [3, 3, 3, 3], arr2 = [3]`	`[3, 3, 3, 3]`	every element in arr1 is the same value
`arr1 = [1000, 0, 1000, 0], arr2 = [0, 1000]`	`[0, 0, 1000, 1000]`	values at the minimum and maximum of the allowed range

Relative Sort Array