Relative Sort Array

LeetCode 1217 | Difficulty: Easy

Easy

Problem Description

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 do not appear in arr2 should be placed at the end of arr1 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]

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

Topics: Array, Hash Table, Sorting, Counting Sort

---

Approach

Hash Map

Use a hash map for O(1) average lookups. Store seen values, frequencies, or indices. The key question: what should I store as key, and what as value?

When to use

Need fast lookups, counting frequencies, finding complements/pairs.

Sorting

Sort the input to bring related elements together or enable binary search. Consider: does sorting preserve the answer? What property does sorting give us?

When to use

Grouping, finding closest pairs, interval problems, enabling two-pointer or binary search.

---

Solutions

Solution 1: C# (Best: 240 ms)

Metric	Value
Runtime	240 ms
Memory	29.3 MB
Date	2019-12-10

Solution

public class Solution {
    public int[] RelativeSortArray(int[] arr1, int[] arr2) {
      int[] cnt = new int[1001]; int[] tmp = new int[arr1.Length];
    for (int i = 0; i < arr1.Length; i++)
    {
        cnt[arr1[i]]++;
    }
    int k=0;
    foreach (var i in arr2)
    {

        while (cnt[i]-- > 0)
        {
            tmp[k++] = i;
        }
    }
    for (int i = 0; i <= 1000; i++)
    {
        while(cnt[i]-->0)
        {
            tmp[k++] = i;
        }
    }
    return tmp;  
    }
}

---

Complexity Analysis

Approach	Time	Space
Sort + Process	$O(n log n)$	$O(1) to O(n)$
Hash Map	$O(n)$	$O(n)$

---

Interview Tips

Key Points

• Start by clarifying edge cases: empty input, single element, all duplicates.
• Hash map gives O(1) lookup — think about what to use as key vs value.
• LeetCode provides 2 hint(s) for this problem — try solving without them first.

💡 Hints

Hint 1: Using a hashmap, we can map the values of arr2 to their position in arr2.

Hint 2: After, we can use a custom sorting function.