Relative Sort Array

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:

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.

Solution

Video

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

<div class="youtube-embed"><iframe src="https://www.youtube.com/embed/2KIunLCXp64" frameborder="0" allowfullscreen></iframe></div>

Guidance

• Prefer the counting-sort / bucket method ([#Method 2 - Using Bucketsort with array](#method-2---using-bucketsort-with-array)) when the value range bound holds (0..1000) — it's O(n) and simple.
• Use the map+sort approach ([#Method 1 - Using Map and Sorting](#method-1---using-map-and-sorting)) when values are unbounded or sparse.
• The sort-and-search variant ([#Method 3 - Sort-and-Search (binary-search + visited)](#method-3---sort-and-search-(binary-search-+-visited))) is educational and useful when you already need a sorted snapshot of arr1, but it's rarely the best practical choice for this problem.

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

C++

#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;
    }
};

Java

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;
    }
}

Python

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

C++

#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;
    }
};

Java

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;
    }
}

Python

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

C++

#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;
    }
};

Java

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();
    }
}

Python

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.