Relative Sort Array

Easy
206.

Relative Sort Array

Relative Sort Array is an easy coding problem on arrays, hash table and sorting, asked in Amazon, Microsoft and Adobe interviews.

Given two arrays arr1 and arr2, where the elements of arr2 are distinct and all of them also appear in arr1, sort arr1 so that its elements follow the same relative order as in arr2.

Any element of arr1 that is not in arr2 goes at the end, in ascending order.

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]

Example 2

Input
arr1 = [28,6,22,8,44,17], arr2 = [22,28,8,6]
Output
[22,28,8,6,17,44]

Example 3

Input
arr1 = [1,1], arr2 = [1]
Output
[1,1]

Constraints

  • 1 <= arr1.length <= 40
  • 1 <= arr2.length <= 40
  • 0 <= arr1[i], arr2[i] <= 100
  • arr2 has distinct elements, each present in arr1.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} arr1
 * @param {number[]} arr2
 * @return {number[]}
 */
var relativeSortArray = function(arr1, arr2) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Relative Sort Array — Solution in Python, Java & C++

Relative Sort Array solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Relative Sort Array is an easy coding problem on arrays, hash table and sorting, asked in Amazon, Microsoft and Adobe interviews.

Problem statement

Given two arrays arr1 and arr2, where the elements of arr2 are distinct and all of them also appear in arr1, sort arr1 so that its elements follow the same relative order as in arr2.

Any element of arr1 that is not in arr2 goes at the end, in ascending order.

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]

Example 2

Input: arr1 = [28,6,22,8,44,17], arr2 = [22,28,8,6]
Output: [22,28,8,6,17,44]

Example 3

Input: arr1 = [1,1], arr2 = [1]
Output: [1,1]

Constraints

  • 1 <= arr1.length <= 40
  • 1 <= arr2.length <= 40
  • 0 <= arr1[i], arr2[i] <= 100
  • arr2 has distinct elements, each present in arr1.

Hints for Relative Sort Array

  1. Hint 1

    Build a map from value to its position in arr2 — that map is the comparison key.

  2. Hint 2

    Split arr1 into the values the map knows and the values it does not.

  3. Hint 3

    Sort the first group by rank and the second group numerically, then join them.

How to solve Relative Sort Array

The order in arr2 defines a rank for each known value; sort the known elements by rank and the unknown ones numerically, then join.

Approach

  1. Build rank[value] = position in arr2.
  2. Sort the elements of arr1 that have a rank by that rank.
  3. Sort the remaining elements numerically and append.

Why it works

Sorting by rank reproduces arr2's order with duplicates kept together, and the leftover group is specified to be ascending.

Complexity

  • Time — O(n log n)
  • Space — O(n)

Pitfalls

  • A counting sort over the bounded value range avoids the comparison sort entirely.
  • Values in arr2 are distinct, so ranks are unambiguous.

Reference solution

Python

def relativeSortArray(arr1, arr2):
    rank = {v: i for i, v in enumerate(arr2)}
    known = sorted([x for x in arr1 if x in rank], key=lambda x: rank[x])
    rest = sorted(x for x in arr1 if x not in rank)
    return known + rest

Java

public static int[] relativeSortArray(int[] arr1, int[] arr2) {
    Set<Integer> inArr2 = new HashSet<>();
    for (int x : arr2) inArr2.add(x);
    List<Integer> out = new ArrayList<>();
    for (int v : arr2) {
        for (int x : arr1) {
            if (x == v) out.add(x);
        }
    }
    List<Integer> rest = new ArrayList<>();
    for (int x : arr1) {
        if (!inArr2.contains(x)) rest.add(x);
    }
    Collections.sort(rest);
    out.addAll(rest);
    int[] res = new int[out.size()];
    for (int i = 0; i < res.length; i++) res[i] = out.get(i);
    return res;
}

C++

vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) {
    unordered_set<int> inArr2(arr2.begin(), arr2.end());
    vector<int> out;
    for (int v : arr2) {
        for (int x : arr1) {
            if (x == v) out.push_back(x);
        }
    }
    vector<int> rest;
    for (int x : arr1) {
        if (!inArr2.count(x)) rest.push_back(x);
    }
    sort(rest.begin(), rest.end());
    for (int x : rest) out.push_back(x);
    return out;
}

JavaScript

var relativeSortArray = function(arr1, arr2) {
    const rank = new Map();
    for (let i = 0; i < arr2.length; i++) rank.set(arr2[i], i);
    const known = [], rest = [];
    for (let i = 0; i < arr1.length; i++) {
        if (rank.has(arr1[i])) known.push(arr1[i]);
        else rest.push(arr1[i]);
    }
    known.sort(function(a, b) { return rank.get(a) - rank.get(b); });
    rest.sort(function(a, b) { return a - b; });
    return known.concat(rest);
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets