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

Examples

Example 1:

1
2

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:

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

Solution

Video

We can either use map + sorting, or TreeMap OR map + heap or bucket to sort this problem. Here is the video explanation:

Guidance

Method 1 - Using Map and Sorting

  1. We can use counts as frequency map on arr1.
  2. Then, we loop on arr2, and if key is present in counts, we append to the present list for value number of times
  3. Then, we check arr2 and counts map to find the keys that don’t exist in arr2 and append them value number of times to notPresent list
  4. Then, we sort notPresent list
  5. Finally, we append notPresent list to present list and that is our answer.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
using namespace std;

class Solution {
public:
    vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) {
        unordered_map<int, int> counts;
        for (int x : arr1) counts[x]++;

        vector<int> present;
        for (int num : arr2) {
            auto it = counts.find(num);
            if (it != counts.end()) {
                while (it->second-- > 0) present.push_back(num);
                counts.erase(num);
            }
        }

        vector<int> notPresent;
        for (auto &p : counts) {
            int k = p.first;
            int cnt = p.second;
            for (int i = 0; i < cnt; ++i) notPresent.push_back(k);
        }
        sort(notPresent.begin(), notPresent.end());

        present.insert(present.end(), notPresent.begin(), notPresent.end());
        return present;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

class Solution {
    public int[] relativeSortArray(int[] arr1, int[] arr2) {
        Map<Integer, Long> counts = Arrays.stream(arr1).boxed().collect(
                Collectors.groupingBy(
                        Function.identity(),
                        HashMap::new, // can be skipped
                        Collectors.counting()
                )
        );

        Set<Integer> set = Arrays.stream(arr2).boxed().collect(Collectors.toSet());

        List<Integer> present = new ArrayList<>();
        for (int num : arr2) {
            long count = counts.get(num);
            for (int i = 0; i < count; i++) {
                present.add(num);
            }
        }

        List<Integer> notPresent = new ArrayList<>();
        for (int k : counts.keySet()) {
            if (!set.contains(k)) {
                long count = counts.get(k);
                for (int i = 0; i < count; i++) {
                    notPresent.add(k);
                }
            }
        }
        notPresent.sort(Comparator.comparingInt(o -> o));

        int n = present.size();
        int m = notPresent.size();

        int[] ans = new int[present.size() + notPresent.size()];

        IntStream.range(0, n).forEach(i -> {
            ans[i] = present.get(i);
        });

        IntStream.range(0, m).forEach(i -> {
            ans[i + n] = notPresent.get(i);
        });
        
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution:
    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:
        counts = Counter(arr1)
        present = []
        for num in arr2:
            cnt = counts.pop(num, 0)
            present.extend([num] * cnt)

        not_present = []
        for k, v in counts.items():
            not_present.extend([k] * v)
        not_present.sort()

        return present + not_present

Complexity

  • ⏰ Time complexity: O(n log n)
  • 🧺 Space complexity: O(n)

Method 2 - Using Bucketsort with array

  1. Because 0 <= arr1[i], arr2[i] <= 1000, we use an array to count every element, lets call it cnt.
  2. Now, we don’t need arr1, we can actually fill the sorted array in place. So, we will go through arr2, from left to right. When, we find frequency of it in cnt, we fill it in arr1.
  3. Now, we fill in remaining elements in cnt, which are not yet encountered.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

#include <vector>
using namespace std;

class Solution {
public:
    vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) {
        vector<int> cnt(1001, 0);
        for (int num : arr1) cnt[num]++;
        int i = 0;
        for (int num : arr2) {
            while (cnt[num]-- > 0) arr1[i++] = num;
        }
        for (int num = 0; num < (int)cnt.size(); ++num) {
            while (cnt[num]-- > 0) arr1[i++] = num;
        }
        return arr1;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    public int[] relativeSortArray(int[] arr1, int[] arr2) {
        int[] cnt = new int[1001];
        for(int num : arr1) {
	        cnt[num]++;
	    }
        int i = 0;
        for(int num : arr2) {
            while(cnt[num]-- > 0) {
                arr1[i++] = num;
            }
        }
        for(int num = 0; num < cnt.length; num++) {
            while(cnt[num]-- > 0) {
                arr1[i++] = num;
            }
        }
        return arr1;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution:
    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:
        cnt = [0] * 1001
        for num in arr1:
            cnt[num] += 1
        res = []
        for num in arr2:
            while cnt[num] > 0:
                res.append(num)
                cnt[num] -= 1
        for num in range(len(cnt)):
            while cnt[num] > 0:
                res.append(num)
                cnt[num] -= 1
        return res

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(n) for using the count array

Method 3 - Sort-and-Search (binary-search + visited)

Intuition

If you prefer working with a sorted auxiliary array, another approach is to sort a copy of arr1, then for every element in arr2 binary-search the first occurrence and copy its duplicates into the output while marking them visited; finally append the leftover (not-visited) elements in sorted order. This is mostly an educational variant — it leverages binary search for locating the starting index of each value and a visited[] array to avoid duplicating elements.

Approach

  1. Copy arr1 into an auxiliary array aux and sort it.
  2. Create a boolean visited array initialized to false.
  3. For each value x in arr2:
    • Binary-search aux for the first index idx where aux[idx] == x.
    • If found, walk forward from idx, append each equal x to the output and mark the positions visited.
  4. After processing all arr2, append all elements in aux whose visited flag is false (they are the not-present elements), which are already in sorted order.

This approach is simple and good for teaching binary search and careful in-place bookkeeping. It’s not asymptotically better than the map+sort method, and counting-sort is preferable when the value range is small.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) {
        int n = arr1.size();
        vector<int> aux = arr1;
        sort(aux.begin(), aux.end());
        vector<char> vis(n, 0);
        vector<int> out; out.reserve(n);

        for (int x : arr2) {
            auto it = lower_bound(aux.begin(), aux.end(), x);
            if (it == aux.end() || *it != x) continue;
            int idx = it - aux.begin();
            while (idx < n && aux[idx] == x) {
                if (!vis[idx]) { out.push_back(x); vis[idx] = 1; }
                ++idx;
            }
        }

        for (int i = 0; i < n; ++i) if (!vis[i]) out.push_back(aux[i]);
        return out;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

import java.util.*;

class Solution {
    public int[] relativeSortArray(int[] arr1, int[] arr2) {
        int n = arr1.length;
        int[] aux = Arrays.copyOf(arr1, n);
        Arrays.sort(aux);
        boolean[] vis = new boolean[n];
        List<Integer> out = new ArrayList<>(n);

        for (int x : arr2) {
            int idx = Arrays.binarySearch(aux, x);
            if (idx < 0) continue;
            // find first occurrence
            while (idx - 1 >= 0 && aux[idx - 1] == x) idx--;
            while (idx < n && aux[idx] == x) {
                if (!vis[idx]) { out.add(x); vis[idx] = true; }
                idx++;
            }
        }

        for (int i = 0; i < n; ++i) if (!vis[i]) out.add(aux[i]);
        return out.stream().mapToInt(Integer::intValue).toArray();
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

from typing import List
import bisect

class Solution:
    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:
        aux = sorted(arr1)
        n = len(aux)
        vis = [False] * n
        out = []

        for x in arr2:
            i = bisect.bisect_left(aux, x)
            if i == n or aux[i] != x:
                continue
            while i < n and aux[i] == x:
                if not vis[i]:
                    out.append(x)
                    vis[i] = True
                i += 1

        for i in range(n):
            if not vis[i]:
                out.append(aux[i])
        return out

Complexity

  • ⏰ Time complexity: O(n log n) – Sorting the auxiliary array dominates; binary searches and linear scans are dominated by the sort.
  • 🧺 Space complexity: O(n) – aux and visited arrays are used.