LeetCode 1122: Relative Sort Array

Problem Description

LeetCode Problem 1122

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.

Difficulty: Easy

Tags: array, hash table, sorting, counting sort

Rating: 94.31%

Solution Approach

The problem can be solved efficiently using a frequency counter (hash map) approach. Here’s how it works:

1. First, I count the frequency of each element in arr1
2. Then, I construct our output array by:
   • Following the order in arr2, using the frequencies from the counter
   • Appending remaining elements in sorted order

Here’s the Python implementation:

class Solution:
    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:
        freq = {}
        for i in arr1:
            freq[i] = freq.get(i, 0) + 1
        
        output = []
        for i in arr2:
            output.extend([i] * freq[i])
            del freq[i]  # Remove used elements from frequency dict
        
        for i in sorted(freq.keys()):
            output.extend([i] * freq[i])
        
        return output

Detailed Walkthrough

Let’s walk through Example 1 step by step:

arr1 = [2,3,1,3,2,4,6,7,9,2,19]
arr2 = [2,1,4,3,9,6]

1. Building frequency dictionary:

   freq = {
       2: 3,  # 2 appears 3 times
       3: 2,  # 3 appears 2 times
       1: 1,  # 1 appears 1 time
       4: 1,  # 4 appears 1 time
       6: 1,  # 6 appears 1 time
       7: 1,  # 7 appears 1 time
       9: 1,  # 9 appears 1 time
       19: 1  # 19 appears 1 time
   }
   

2. Following arr2’s order:

   • For 2: Add [2,2,2] to output
   • For 1: Add [1] to output
   • For 4: Add [4] to output
   • For 3: Add [3,3] to output
   • For 9: Add [9] to output
   • For 6: Add [6] to output

   After this step: output = [2,2,2,1,4,3,3,9,6]

3. Remaining elements:

   • freq now only contains {7: 1, 19: 1}
   • Sort these keys: [7, 19]
   • Add remaining elements: [7, 19]

Final output: [2,2,2,1,4,3,3,9,6,7,19]

Complexity Analysis

• Time Complexity: $O(n log n)$, where n is the length of arr1

  • Building frequency dictionary: O(n)
  • Processing arr2 elements: O(n)
  • Sorting remaining elements: O(k log k), where k is the number of elements not in arr2

• Space Complexity: $O(n)$

  • Frequency dictionary: O(n)
  • Output array: O(n)