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.

Description Hints 2 Solution Video 7:32

1122. Relative Sort Array

Easy75.4% acceptance6 companies

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.

Asked at 6 companies

D. E. Shaw Walmart Labs Meta

Google Amazon Bloomberg

Topics

Hints open one at a time

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.

7:32

Still stuck?Read 4 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

[2,3,1,3,2,4,6,7,9,2,19]
[2,1,4,3,9,6]

Input

[28,6,22,8,44,17]
[22,28,8,6]

Your code is saved on this device.Solution