#1122

Easy

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Relative Sort Array

Sort arr1 by the relative order of arr2, with remaining elements placed in ascending order.

Problem Statement

Given two arrays, arr1 and arr2, where all elements of arr2 are distinct and also present in arr1, the task is to reorder arr1 based on the order of elements in arr2. The relative ordering of elements in arr1 should match the order of arr2, and the elements of arr1 that are not in arr2 should be placed at the end, in ascending order.

For example, if arr1 = [2,3,1,3,2,4,6,7,9,2,19] and arr2 = [2,1,4,3,9,6], the correct output is [2,2,2,1,4,3,3,9,6,7,19]. The elements of arr1 are reordered such that the elements appearing in arr2 appear first, preserving their relative order, and any remaining elements from arr1 are sorted 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 details omitted.

Example 2

Input: arr1 = [28,6,22,8,44,17], arr2 = [22,28,8,6]

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

Example details omitted.

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 Approach

Hashmap for Ordering

Use a hashmap to map each element in arr2 to its index. This allows us to maintain the relative order of the elements from arr2 when rearranging arr1.

Array Scanning and Sorting

Traverse arr1, and for each element that exists in arr2, place it in its respective position in the output array. Afterward, elements not in arr2 are sorted and added to the end.

Final Merging

Once the elements from arr2 are positioned correctly in arr1, append the remaining elements that don't appear in arr2, and sort them in ascending order before adding them to the result.

Complexity Analysis

Metric	Value
Time	O(n + m + k)
Space	O(k)

The time complexity is O(n + m + k), where n is the length of arr1, m is the length of arr2, and k is the number of elements not in arr2. The space complexity is O(k) due to the storage of remaining elements in arr1 that aren't in arr2 and need to be sorted.

What Interviewers Usually Probe

Look for an efficient implementation that minimizes unnecessary sorting.
Test the candidate's ability to use a hashmap for ordering and scanning.
Check how the candidate handles edge cases, such as when arr1 and arr2 are the same length.

Common Pitfalls or Variants

Common pitfalls

Failing to account for elements in arr1 that aren't in arr2, leading to incorrect output.
Not maintaining the relative order of elements in arr1 that match arr2.
Not sorting the leftover elements of arr1 correctly at the end.

Follow-up variants

Handling cases where arr1 and arr2 contain repeated elements.
Optimizing space usage if constraints change, such as limiting space complexity to O(1).
Implementing a version that sorts arr1 directly without using a hashmap.

FAQ

How does the relative ordering of elements work in the 'Relative Sort Array' problem?

The relative ordering of elements in arr1 must match the order of elements in arr2. Elements not in arr2 are placed at the end, in ascending order.

What is the main pattern used in the 'Relative Sort Array' problem?

The main pattern is array scanning combined with hash lookup. A hashmap is used to track the order of elements from arr2, and scanning arr1 ensures elements are placed correctly.

How do we handle elements in arr1 that aren't in arr2?

Elements in arr1 that aren't in arr2 should be placed at the end and sorted in ascending order before appending them to the result.

What is the time complexity of the 'Relative Sort Array' problem?

The time complexity is O(n + m + k), where n is the length of arr1, m is the length of arr2, and k is the number of elements not in arr2.

How does GhostInterview help with the 'Relative Sort Array' problem?

GhostInterview helps by providing a clear breakdown of the solution approach and common pitfalls, assisting you in writing optimized code and debugging efficiently.

terminal

Solution

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

1

2

3

4

class Solution:
    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:
        pos = {x: i for i, x in enumerate(arr2)}
        return sorted(arr1, key=lambda x: pos.get(x, 1000 + x))

Solution 2: Counting Sort

We can use the idea of counting sort. First, count the occurrence of each element in array $arr1$. Then, according to the order in array $arr2$, put the elements in $arr1$ into the answer array $ans$ according to their occurrence. Finally, we traverse all elements in $arr1$ and put the elements that do not appear in $arr2$ in ascending order at the end of the answer array $ans$.

1

2

3

4

class Solution:
    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:
        pos = {x: i for i, x in enumerate(arr2)}
        return sorted(arr1, key=lambda x: pos.get(x, 1000 + x))

Continue Practicing

#1365 how many numbers are smaller than the current number #1090 largest values from labels #1169 invalid transactions