Problem Description

You are given two integer arrays arr1 and arr2 where:

• All elements in arr2 are distinct (no duplicates)
• Every element in arr2 also exists in arr1

Your task is to sort arr1 according to the following rules:

1. For elements that appear in both arrays: Sort them in arr1 based on their order in arr2. If element a appears before element b in arr2, then a should appear before b in the sorted arr1.

2. For elements that only appear in arr1: Place them at the end of the sorted array 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 output would be [2,2,2,1,4,3,3,9,6,7,19] because:

• Elements 2,1,4,3,9,6 are sorted according to their order in arr2
• Elements 7,19 (which don't appear in arr2) are placed at the end in ascending order

The solution uses a custom sorting approach by creating a position mapping for elements in arr2. Each element in arr1 is assigned a sorting key: if it exists in arr2, it gets its position index; otherwise, it gets a large value (1000 + x) to ensure it appears at the end while maintaining ascending order among elements not in arr2.

Intuition

The core challenge is to sort arr1 based on two different criteria: elements in arr2 follow a custom order, while elements not in arr2 follow standard ascending order.

Think of this as creating a priority system. Elements that appear in arr2 have higher priority and should come first, ordered according to their position in arr2. Elements not in arr2 have lower priority and should come last, sorted numerically.

To achieve this dual sorting behavior, we can leverage Python's built-in sorted() function with a custom key. The key insight is to map each element to a value that represents its sorting priority:

1. For elements in arr2: We assign them their position index (0, 1, 2, ...). This ensures they maintain the same relative order as in arr2.

2. For elements not in arr2: We need to assign them values that are guaranteed to be larger than any position index from arr2. By using 1000 + x, we ensure these elements will be placed after all elements from arr2 (since arr2 can have at most 1000 elements based on typical constraints).

The beauty of this approach is that 1000 + x not only pushes these elements to the end but also preserves their natural ascending order. For example, if we have elements 7 and 19 not in arr2, they'll get keys 1007 and 1019 respectively, maintaining 7 < 19 in the final sorted result.

This transforms our complex two-criteria sorting problem into a simple single-key sorting problem, where the key function lambda x: pos.get(x, 1000 + x) elegantly handles both cases in one expression.

Learn more about Sorting patterns.

Solution Approach

The implementation uses a hash table and custom sorting to achieve the desired result. Let's break down the solution step by step:

Step 1: Create Position Mapping

pos = {x: i for i, x in enumerate(arr2)}

We build a dictionary pos that maps each element in arr2 to its index position. For example, if arr2 = [2,1,4,3], then pos = {2:0, 1:1, 4:2, 3:3}. This allows us to quickly look up the desired position for any element that appears in arr2.

Step 2: Sort with Custom Key Function

return sorted(arr1, key=lambda x: pos.get(x, 1000 + x))

We sort arr1 using a custom key function. For each element x in arr1, the key function works as follows:

• If x exists in pos (meaning it's in arr2), use pos[x] as the sorting key
• If x doesn't exist in pos, use 1000 + x as the sorting key

How the Sorting Works: When Python's sorted() function compares elements, it actually compares their key values:

• Elements from arr2 get keys in range [0, len(arr2)-1]
• Elements not in arr2 get keys starting from 1000

For example, with arr1 = [2,3,1,3,2,4] and arr2 = [2,1,4]:

• Element 2 → key = 0
• Element 1 → key = 1
• Element 4 → key = 2
• Element 3 → key = 1003 (not in arr2)

After sorting by these keys: [0,0,1,2,1003,1003], we get the final array: [2,2,1,4,3,3].

Time Complexity: O(n log n) where n is the length of arr1, dominated by the sorting operation.

Space Complexity: O(m) where m is the length of arr2, for storing the position mapping.

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Given:

• arr1 = [5, 3, 1, 2, 3, 5, 6]
• arr2 = [3, 1, 5]

Step 1: Create Position Mapping

First, we build a dictionary that maps each element in arr2 to its position:

pos = {3: 0, 1: 1, 5: 2}

This tells us that 3 should come first (position 0), 1 should come second (position 1), and 5 should come third (position 2).

Step 2: Assign Sorting Keys

Now, for each element in arr1, we determine its sorting key:

Step 3: Sort by Keys

We sort the elements based on their keys:

• Keys in order: [0, 0, 1, 2, 2, 1002, 1006]
• Corresponding elements: [3, 3, 1, 5, 5, 2, 6]

Notice how:

• Elements with the same key (like both 3s with key 0) maintain their relative order
• Elements from arr2 (keys 0-2) come before elements not in arr2 (keys 1002+)
• Elements not in arr2 (2 and 6) are sorted in ascending order at the end

Final Result: [3, 3, 1, 5, 5, 2, 6]

This matches our expected output where elements follow the order defined by arr2 = [3, 1, 5], and remaining elements [2, 6] are appended in ascending order.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × log n + m)

The time complexity breaks down as follows:

• Creating the position dictionary pos from arr2 takes O(m) time, where m is the length of arr2
• Sorting arr1 using Python's built-in sorted() function takes O(n × log n) time, where n is the length of arr1
• During sorting, the key function lambda x: pos.get(x, 1000 + x) is called O(n) times, and each dictionary lookup takes O(1) average time
• Therefore, the total time complexity is O(m) + O(n × log n) = O(n × log n + m)

Space Complexity: O(n + m)

The space complexity consists of:

• The dictionary pos stores all elements from arr2, requiring O(m) space
• The sorted() function creates a new sorted list containing all elements from arr1, requiring O(n) space
• The sorting algorithm itself (Timsort in Python) uses O(n) auxiliary space in the worst case
• Therefore, the total space complexity is O(m) + O(n) = O(n + m)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Overflow Risk with the Offset Value

The solution uses 1000 + x as the sorting key for elements not in arr2. This approach has a critical assumption that could lead to incorrect results.

The Problem: If elements in arr2 have very large indices (e.g., if arr2 has more than 1000 elements), or if the values in arr1 that don't appear in arr2 are negative, the sorting keys could overlap or be ordered incorrectly.

Example of Failure:

• If arr2 has 1500 elements, the last element would have key 1499
• An element with value 400 not in arr2 would have key 1400
• This would incorrectly place the non-arr2 element before some arr2 elements

Solution: Use a more robust offset that guarantees separation:

def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:
    position_map = {element: index for index, element in enumerate(arr2)}
    # Use length of arr2 as offset base, then add a large constant
    offset = len(arr2) + 10001  # Handles constraint: -1000 <= arr1[i] <= 1000
    return sorted(arr1, key=lambda x: position_map.get(x, offset + x))

2. Not Preserving Original Order for Duplicate Elements

While Python's sorted() is stable (preserves relative order of equal elements), relying on this behavior without understanding it can lead to confusion when implementing in other languages.

Better Approach for Clarity: Explicitly handle the counting and reconstruction:

def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:
    from collections import Counter
    count = Counter(arr1)
    result = []
  
    # Add elements from arr2 in order
    for num in arr2:
        result.extend([num] * count[num])
        del count[num]
  
    # Add remaining elements in ascending order
    for num in sorted(count.keys()):
        result.extend([num] * count[num])
  
    return result

3. Assuming Input Constraints Without Validation

The solution assumes all elements in arr2 exist in arr1 as stated in the problem. In real-world scenarios, this assumption might not hold.

Defensive Programming: Add validation if needed:

def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:
    position_map = {element: index for index, element in enumerate(arr2)}
    # Validate assumption (optional based on requirements)
    arr1_set = set(arr1)
    for element in arr2:
        if element not in arr1_set:
            raise ValueError(f"Element {element} from arr2 not found in arr1")
  
    offset = len(arr2) + 10001
    return sorted(arr1, key=lambda x: position_map.get(x, offset + x))