1122. Relative Sort Array
Model: qwen2.5-coder:14b
Topics: Array,Sort
FAANG asked: 1
Acceptance rate: 68.2%
Problem Breakdown
The problem requires sorting the elements of arr1 based on their order in arr2. Elements that appear in both arrays should maintain their relative order from arr2, while elements unique to arr1 should be appended at the end, sorted in ascending order. The constraints are that both arrays have lengths between 1 and 1000, and all elements are non-negative integers up to 1000.
Inputs:
arr1: An array of integers.arr2: An array of distinct integers, where each element is also inarr1.
Outputs:
- A sorted version of
arr1based on the order defined byarr2, with remaining elements sorted at the end.
Implicit Constraints/Edge Cases:
- If
arr2is empty, returnarr1sorted. - If all elements in
arr1are inarr2, maintain their relative order fromarr2. - Elements not in
arr2should be sorted and appended at the end.
Intuition
A brute-force approach would involve sorting arr1 using a custom comparator that checks against arr2. However, this could lead to inefficient comparisons, especially if arr1 is much larger than arr2.
The key insight is to use a counting sort-like approach. Since the elements are bounded by 1000, we can count occurrences of each element in arr1, then reconstruct the sorted array based on the order defined by arr2. This avoids the need for complex comparisons and leverages the small range of possible values.
Approach
- Count Occurrences: Use a dictionary to count how many times each element appears in
arr1. - Construct Sorted Array:
- Iterate through
arr2and append elements fromarr1according to their counts, maintaining the order. - For elements not in
arr2, collect them separately and sort them. - Append the sorted unique elements at the end of the result.
- Iterate through
This approach ensures that we efficiently sort arr1 while adhering to the relative order defined by arr2.
Complexity Analysis
- Time Complexity: O(n + m log m), where n is the length of
arr1and m is the number of unique elements not inarr2. Counting occurrences takes O(n), iterating througharr2takes O(n) (since we append each element according to its count), and sorting the unique elements takes O(m log m). - Space Complexity: O(n + m), where n is used for counting occurrences, and m is for storing unique elements.
Solution
def relativeSortArray(arr1, arr2):
# Step 1: Count occurrences of each element in arr1
count = {}
for num in arr1:
if num in count:
count[num] += 1
else:
count[num] = 1
# Step 2: Construct the sorted array based on arr2
result = []
for num in arr2:
if num in count:
result.extend([num] * count[num])
del count[num]
# Step 3: Collect and sort elements not in arr2
unique_elements = [num for num in count.keys()]
unique_elements.sort()
# Step 4: Append sorted unique elements to the result
for num in unique_elements:
result.extend([num] * count[num])
return result
# Example usage
arr1 = [2,3,1,3,2,4,6,7,9,2,19]
arr2 = [2,1,4,3,9,6]
print(relativeSortArray(arr1, arr2)) # Output: [2,2,2,1,4,3,3,9,6,7,19]
Edge Cases Handled
- Empty
arr2: Ifarr2is empty, the result will bearr1sorted in ascending order. - All elements in
arr1are inarr2: The relative order fromarr2is maintained. - Unique elements in
arr1: These are collected, sorted, and appended at the end.