Relative Sort Array solution and explanation
Google
9 more videos on this problem
Relative Sort Array - Leetcode 1122 - PythonNeetCodeIO · 7:32 · 11K views
Relative Sort Array | Counting Sort | Using Lambda | Leetcode 1122 | codestorywithMIKcodestorywithMIK · 20:15 · 7K views
1122. Relative Sort Array (Leetcode Easy)Programming Live with Larry · 4:01 · 2K views
LeetCode 1122. Relative Sort Array | JSer - JavaScript & AlgorithmJSer · 5:41 · 699 views
Relative Sort Array - Leetcode 1122 - JavaCode With K5KC · 9:30 · 313 views
Daily Leetcode #1533: Jun 11, 2024 - 1122. Relative Sort ArrayProgramming Live with Larry · 5:09 · 222 views
Leetcode 1122 Relative Sort ArrayMath Geeks · 4:08 · 152 views
Leetcode 1122: Relative Sort ArrayAlgorithms Casts · 10:02 · 116 views
LeetCode 1122 - Relative Sort Array - JavaAlpha-Code · 5:59 · 108 views
LeetCode 1122 Relative Sort Array|| Day 74||C++ ||Easy ||Leetcode ||Code With DeepaCode With Deepa · 9:33 · 106 views
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 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 <= 10000 <= arr1[i], arr2[i] <= 1000- All the elements of
arr2are distinct. - Each
arr2[i]is inarr1.
Approach overview
Problem Overview: You receive two arrays: arr1 and arr2. All elements of arr2 are distinct and also appear in arr1. Reorder arr1 so elements appear in the same relative order as arr2. Any values not present in arr2 must be placed at the end in ascending order.
Approach 1: Counting Sort with HashMap (O(n + k) time, O(k) space)
This approach uses frequency counting. First iterate through arr1 and build a frequency map (or counting array since values are small). Then iterate through arr2 and append each value to the result as many times as its frequency indicates. Decrease the count each time you place a value. After processing all arr2 elements, collect the remaining numbers from the frequency structure and append them in sorted order.
The key insight: elements in arr2 define a priority order. Counting frequencies lets you output them without repeated searches or comparisons. Because the value range is limited, this behaves like counting sort. Time complexity is O(n + k) where n is the size of arr1 and k is the value range. Space complexity is O(k). This technique combines ideas from hash tables and counting sort.
Approach 2: Custom Comparator Sorting (O(n log n) time, O(1) extra space)
Another option is to sort arr1 using a custom comparator. Build a map from value → index representing each element's position in arr2. During sorting, if both elements exist in the map, compare their mapped indices to preserve arr2's order. If only one element exists in the map, prioritize it before elements not present in arr2. If neither element exists in the map, compare them normally so they appear in ascending order.
This method relies entirely on the language's built-in sorting algorithm. The comparator encodes the problem rules. Time complexity is O(n log n) due to sorting. Space complexity is O(m) for the index map where m is the size of arr2.
Recommended for interviews: The counting sort approach is usually the expected optimal solution. It runs in linear time and shows you recognize the bounded value range. The custom comparator solution is still acceptable and often easier to implement quickly, but it is less optimal because of the O(n log n) sorting step. Mentioning both demonstrates strong problem-solving depth.
Approach 1: Counting Sort with HashMap
This approach uses a hash map (or dictionary) to count the occurrences of each element in arr1. Then, it constructs a new listby first adding elements in the order they appear in arr2 based on their count, and then adding remaining elements in sorted order.
def relative_sort_array(arr1, arr2):
count = {x: 0 for x in arr2}
others = []
for number in arr1:
if number in count:
count[number] += 1
else:
others.append(number)
result = []
for number in arr2:
result.extend([number] * count[number])
return result + sorted(others)
# Example usage
arr1 = [2,3,1,3,2,4,6,7,9,2,19]
arr2 = [2,1,4,3,9,6]
print(relative_sort_array(arr1, arr2)) # Output: [2, 2, 2, 1, 4, 3, 3, 9, 6, 7, 19]function relativeSortArray(arr1, arr2) {
const countMap = new Map();
const others = [];
arr2.forEach(num => countMap.set(num, 0));
arr1.forEach(num => {
if (countMap.has(num)) {
countMap.set(num, countMap.get(num) + 1);
} else {
others.push(num);
}
});
const result = [];
arr2.forEach(num => {
result.push(...Array(countMap.get(num)).fill(num));
});
return result.concat(others.sort((a, b) => a - b));
}
// Example usage
console.log(relativeSortArray([2,3,1,3,2,4,6,7,9,2,19], [2,1,4,3,9,6]));
// Output: [2, 2, 2, 1, 4, 3, 3, 9, 6, 7, 19]This code creates a dictionary to count occurrences of elements present in arr2 and compiles a list of elements that are only in arr1.
Firstly, it iterates over arr1 to populate the dictionary and the extra elements list.
The function then iterates over arr2 and appends each number to the result list based on the count recorded in the dictionary.
Finally, the function appends the sorted extra elements to the result.
Time Complexity: O(n log n), dominated by the sorting of extra elements not in arr2.
Space Complexity: O(n), primarily due to the dictionary and list of extra elements.
Approach 2: Custom Comparator Sorting
Utilize a custom comparator function to sort arr1 according to the order defined in arr2, with arr1 elements not in arr2 sorted at the end.
import java.util.*;
public class RelativeSort {
public int[] relativeSortArray(int[] arr1, int[] arr2) {
Map<Integer, Integer> rank = new HashMap<>();
for (int i = 0; i < arr2.length; i++) {
rank.put(arr2[i], i);
}
Integer[] arr1Integer = Arrays.stream(arr1).boxed().toArray(Integer[]::new);
Arrays.sort(arr1Integer, (x, y) -> {
if (rank.containsKey(x) && rank.containsKey(y))
return rank.get(x) - rank.get(y);
if (rank.containsKey(x))
return -1;
if (rank.containsKey(y))
return 1;
return x - y;
});
return Arrays.stream(arr1Integer).mapToInt(Integer::intValue).toArray();
}
public static void main(String[] args) {
RelativeSort solution = new RelativeSort();
int[] arr1 = {2,3,1,3,2,4,6,7,9,2,19};
int[] arr2 = {2,1,4,3,9,6};
System.out.println(Arrays.toString(solution.relativeSortArray(arr1, arr2)));
}
}#include <vector>
#include <unordered_map>
#include <algorithm>
std::vector<int> relativeSortArray(std::vector<int>& arr1, std::vector<int>& arr2) {
std::unordered_map<int, int> rank;
for (int i = 0; i < arr2.size(); ++i) {
rank[arr2[i]] = i;
}
std::sort(arr1.begin(), arr1.end(), [&rank](int x, int y) {
if (rank.count(x) && rank.count(y))
return rank[x] < rank[y];
if (rank.count(x))
return true;
if (rank.count(y))
return false;
return x < y;
});
return arr1;
}
// Example usage:
// std::vector<int> arr1 = {2,3,1,3,2,4,6,7,9,2,19};
// std::vector<int> arr2 = {2,1,4,3,9,6};
// std::vector<int> output = relativeSortArray(arr1, arr2);In Java, a HashMap assigns rank to arr2 elements, which is leveraged by the custom comparator during sort execution.
It enables a proper order by first distinguishing presence in arr2 and then by lexicographical placement for arr1's other numbers.
Time Complexity: O(n log n) due to the sort process.
Space Complexity: O(n) necessitated by the HashMap.
Approach 3: Custom Sorting
First, we use a hash table pos to record the position of each element in array arr2. Then, we map each element in array arr1 to a tuple (pos.get(x, 1000 + x), x), and sort these tuples. Finally, we take out the second element of all tuples and return it.
The time complexity is O(n times log n + m), and the space complexity is O(n + m). Here, n and m are the lengths of arrays arr1 and arr2, respectively.
function relativeSortArray(arr1: number[], arr2: number[]): number[] {
const pos: Map<number, number> = new Map();
for (let i = 0; i < arr2.length; ++i) {
pos.set(arr2[i], i);
}
const arr: number[][] = [];
for (const x of arr1) {
const j = pos.get(x) ?? arr2.length;
arr.push([j, x]);
}
arr.sort((a, b) => a[0] - b[0] || a[1] - b[1]);
return arr.map(a => a[1]);
}func relativeSortArray(arr1 []int, arr2 []int) []int {
pos := map[int]int{}
for i, x := range arr2 {
pos[x] = i
}
arr := make([][2]int, len(arr1))
for i, x := range arr1 {
if p, ok := pos[x]; ok {
arr[i] = [2]int{p, x}
} else {
arr[i] = [2]int{len(arr2), x}
}
}
sort.Slice(arr, func(i, j int) bool {
return arr[i][0] < arr[j][0] || arr[i][0] == arr[j][0] && arr[i][1] < arr[j][1]
})
for i, x := range arr {
arr1[i] = x[1]
}
return arr1
}class Solution {
func relativeSortArray(_ arr1: [Int], _ arr2: [Int]) -> [Int] {
var pos = [Int: Int]()
for (i, x) in arr2.enumerated() {
pos[x] = i
}
var arr = [(Int, Int)]()
for x in arr1 {
let j = pos[x] ?? arr2.count
arr.append((j, x))
}
arr.sort { $0.0 < $1.0 || ($0.0 == $1.0 && $0.1 < $1.1) }
return arr.map { $0.1 }
}
}Approach 4: Counting Sort
function relativeSortArray(arr1: number[], arr2: number[]): number[] {
const cnt = Array(1001).fill(0);
let mi = Number.POSITIVE_INFINITY;
let mx = Number.NEGATIVE_INFINITY;
for (const x of arr1) {
cnt[x]++;
mi = Math.min(mi, x);
mx = Math.max(mx, x);
}
const ans: number[] = [];
for (const x of arr2) {
while (cnt[x]) {
cnt[x]--;
ans.push(x);
}
}
for (let i = mi; i <= mx; i++) {
while (cnt[i]) {
cnt[i]--;
ans.push(i);
}
}
return ans;
}func relativeSortArray(arr1 []int, arr2 []int) []int {
cnt := make([]int, 1001)
mi, mx := 1001, 0
for _, x := range arr1 {
cnt[x]++
mi = min(mi, x)
mx = max(mx, x)
}
ans := make([]int, 0, len(arr1))
for _, x := range arr2 {
for cnt[x] > 0 {
ans = append(ans, x)
cnt[x]--
}
}
for x := mi; x <= mx; x++ {
for cnt[x] > 0 {
ans = append(ans, x)
cnt[x]--
}
}
return ans
}class Solution {
func relativeSortArray(_ arr1: [Int], _ arr2: [Int]) -> [Int] {
var pos = [Int: Int]()
for (i, x) in arr2.enumerated() {
pos[x] = i
}
var arr = [(Int, Int)]()
for x in arr1 {
let j = pos[x] ?? arr2.count
arr.append((j, x))
}
arr.sort { $0.0 < $1.0 || ($0.0 == $1.0 && $0.1 < $1.1) }
return arr.map { $0.1 }
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Counting Sort with HashMap | Time Complexity: O(n log n), dominated by the sorting of extra elements not in arr2. |
| Custom Comparator Sorting | Time Complexity: O(n log n) due to the sort process. |
| Custom Sorting | – |
| Counting Sort | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Counting Sort with Frequency Map | O(n + k) | O(k) | Best choice when element range is limited and you want linear time performance |
| Custom Comparator Sorting | O(n log n) | O(m) | Good when using built-in sorting utilities or when counting range assumptions are unknown |
Frequently asked questions
Is Relative Sort Array easy or hard?
Relative Sort Array is classified as an Easy problem on LeetCode. The core idea is recognizing that arr2 defines a priority ordering and that counting frequencies avoids expensive repeated searches.
How to solve Relative Sort Array in O(n)?
Use counting sort. Build a frequency array or hash map for arr1, iterate through arr2 to place elements in the required order, then append leftover values sorted by numeric order. Since each element is processed a constant number of times, the complexity becomes O(n + k).
What is the best approach for Relative Sort Array?
Counting sort with a frequency map is the optimal approach. Count occurrences of each number in arr1, output elements following arr2's order, then append remaining values in ascending order. This runs in O(n + k) time where k is the value range.
Is Relative Sort Array asked at Google/Amazon/Meta?
Relative Sort Array appears frequently in coding interviews and online assessments because it tests understanding of hashing and sorting strategies. Variants have appeared in interviews at companies like Amazon and other large tech firms.
What data structure is used in Relative Sort Array?
Common solutions use a hash map or counting array to store frequencies of elements from arr1. Some implementations also use an index map for arr2 when applying a custom sorting comparator.
What is the time complexity of Relative Sort Array?
The optimal counting sort solution runs in O(n + k) time and O(k) space. A comparator-based sorting approach runs in O(n log n) time because it relies on the standard sorting algorithm.
Relative Sort Array Python or Java solution approach
Python solutions usually implement counting sort using collections.Counter or a fixed-size frequency array. Java solutions often use HashMap with counting logic or Arrays.sort with a custom comparator mapping arr2 positions.