Relative Sort Array

While studying for interviews, I’ve been practicing my algorithm skills on LeetCode and other sites quite a bit. Read on for a walkthrough of my JavaScript solution to the Relative Sort Array problem on LeetCode (instructions from LeetCode are below).

The Problem

Given two arrays arr1 and arr2, the elements of arr2 are distinct, and all elements in arr2 are also in arr1.

Sort the elements of arr1 such that the relative ordering of items in arr1 are the same as in arr2. Elements that don't appear in arr2 should be placed at the end of arr1 in ascending order.

Constraints:

• arr1.length, arr2.length <= 1000
• 0 <= arr1[i], arr2[i] <= 1000
• Each arr2[i] is distinct.
• Each arr2[i] is in arr1.

Example 1:

Input: arr1 = [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]

The Solution

The solution we’ll be going over is divided into several parts. In the first few parts, we’ll be creating a Set from the values in arr2 and populating two arrays with values from arr1. In the final part, we’ll add the contents of these two arrays together and make some final adjustments to produce our return value.

Let’s start off by creating two empty arrays. One will contain the values that are present in both arr1 and arr2, and one will store the auxiliary values which are only present in arr1. We can also create a new Set to hold the values of the elements in arr2 to allow for an easy lookup later on. We’ll loop over arr2 and add every element in the array to our Set.

var relativeSortArray = function(arr1, arr2) {
   let sortedArr = [];
   let auxArr = [];
   let arrSet = new Set();
   for (let i = 0; i < arr2.length; i++) {
      arrSet.add(arr2[i];
   }
}

Next, let’s determine which elements in arr1 are also in arr2, and add them to sortedArr in the same order as they appear in arr2. We’ll use a nested for loop here; the outer loop will go over arr2, and the inner loop will move through arr1, with both indexes starting at 0.

As we move through the loops, if the element at the current index of arr1 is equal to the element at the current index of arr2, we will push that element of arr1 into sortedArr. Because the index at arr2 will not change until all elements in arr1 have been inspected for a match (and pushed into sortedArr if matching), we can preserve the order of the elements in arr2 when we’re adding to sortedArr.

for (let i = 0; i < arr2.length; i++) {
       for (let j = 0; j < arr1.length; j++) {
           if (arr1[j] === arr2[i]) {
               sortedArr.push(arr1[j]);
           }
       } 
}

Great, now we have the first part of the solution! Let’s keep going to populate our auxiliary array with values in arr1 which are not present in arr2.

We can loop through arr1 and check arrSet for the element at the current index of arr1. If the element is not in arrSet, we will push it into auxArr.

for (let i = 0; i < arr1.length; i++) {
        if (!arrSet.has(arr1[i])) {
               auxArr.push(arr1[i]);
        }
}

We’re almost done! All we need to do now is to sort auxArr in ascending order and add the two arrays together. We can use the built-in Array.concat() function to add the sorted auxArr to the end of sortedArr, which we will return.

let sortedAux = auxArr.sort((a, b) => a - b);
return sortedArr.concat(sortedAux);

Let’s check out our completed solution! Please note it has been slightly refactored to separate the arrSet population loop from the main function. The runtime of this solution is O(n²).

Problem solved!

You can find the problem on LeetCode here!

Thanks for reading!