How do you solve Relative Sort Array on LeetCode?

Relative Sort Array (LeetCode #1122) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n + k log k) time complexity and O(n) space complexity. Key insight: Using a counting array is efficient for problems with a limited range of integers.

What is the brute force solution for Relative Sort Array?

The brute force approach for Relative Sort Array is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach involves sorting arr1 based on the order defined in arr2. We can achieve this by creating a custom sorting function that prioritizes elements in arr2 and places the remaining elements at the end in ascending order. The optimal Optimal Solution approach improves this to O(n + k log k).

What algorithm or data structure is used to solve Relative Sort Array?

Relative Sort Array uses the following concepts: Array, Hash Table, Sorting, Counting Sort. The recommended patterns to study are: Hash Map, Array.

What are the interview tips for Relative Sort Array?

Clarify the constraints and edge cases before diving into coding. Discuss the time and space complexities of your approach. Consider alternative approaches and their trade-offs.

What are common mistakes when solving Relative Sort Array?

Not handling elements not in arr2 correctly. Forgetting to sort remaining elements in ascending order.

#1122

Relative Sort Array

Easy

ArrayHash TableSortingCounting SortHash MapArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n + k log k)
Space	O(1)	O(n)

💡

Intuition

Time O(n + k log k)Space O(n)

The optimal solution uses a counting sort approach. We count the occurrences of each number in arr1 and then build the result based on the order defined in arr2, followed by sorting the remaining elements.

⚙️

Algorithm

4 steps

1Step 1: Create a count array to count occurrences of each number in arr1.
2Step 2: Initialize an empty result array.
3Step 3: Append elements from arr2 to the result based on their counts.
4Step 4: Append remaining elements (not in arr2) sorted in ascending order.

solution.py11 lines

1def relativeSortArray(arr1, arr2):
2    count = [0] * 1001
3    for num in arr1:
4        count[num] += 1
5    result = []
6    for num in arr2:
7        result.extend([num] * count[num])
8    for num in range(1001):
9        if count[num] > 0 and num not in arr2:
10            result.extend([num] * count[num])
11    return result

ℹ

Complexity note: The time complexity is O(n) for counting and O(k log k) for sorting the remaining elements, where n is the length of arr1 and k is the number of unique elements not in arr2.

1Using a counting array is efficient for problems with a limited range of integers.
2Maintaining the order of elements based on a reference array is crucial.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.