Domain 1EasyCORE

Relative Sort Array

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.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Array#Sort

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 in arr1.

Outputs:

  • A sorted version of arr1 based on the order defined by arr2, with remaining elements sorted at the end.

Implicit Constraints/Edge Cases:

  • If arr2 is empty, return arr1 sorted.
  • If all elements in arr1 are in arr2, maintain their relative order from arr2.
  • Elements not in arr2 should 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

  1. Count Occurrences: Use a dictionary to count how many times each element appears in arr1.
  2. Construct Sorted Array:
    • Iterate through arr2 and append elements from arr1 according 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.

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 arr1 and m is the number of unique elements not in arr2. Counting occurrences takes O(n), iterating through arr2 takes 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: If arr2 is empty, the result will be arr1 sorted in ascending order.
  • All elements in arr1 are in arr2: The relative order from arr2 is maintained.
  • Unique elements in arr1: These are collected, sorted, and appended at the end.