We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Relative Sort Array

Number: 1217

Difficulty: Easy

Paid? No

Companies: Amazon, Bloomberg, Meta, DE Shaw

Problem Description

Given two arrays arr1 and arr2 where arr2 contains distinct elements and every element in arr2 is also in arr1, sort arr1 so that the relative ordering of elements in arr2 is preserved in arr1. Any elements in arr1 that do not appear in arr2 should be placed at the end of arr1 in ascending order.

Key Insights

  • Use a hash table (or array for counting given the value constraints) to count the occurrences of each element in arr1.
  • Iterate through arr2 and for each element, append it to the result based on its count from the hash table.
  • Remove the used elements from the hash table.
  • Sort the remaining elements (those not in arr2) in ascending order and append them to the result.

Space and Time Complexity

Time Complexity: O(n + m log m) where n is the length of arr1 and m is the number of leftover elements not in arr2. Given that element values are bounded (0 to 1000), a counting sort can make this nearly O(n). Space Complexity: O(n) for storing the frequency counts and the result array.

Solution

The solution leverages a frequency counter (hash table) to count how many times each element appears in arr1. We then process arr2 to add each number in its given order according to its frequency. Finally, we sort the remaining numbers that are not in arr2 and append them to the result array. This approach ensures that the relative order specified by arr2 is maintained and that the other elements are sorted in ascending order.

Code Solutions

# Python solution using a frequency dictionary

def relativeSortArray(arr1, arr2):
    # Count frequency of each element in arr1
    count = {}
    for num in arr1:
        count[num] = count.get(num, 0) + 1

    result = []
    # Process elements defined in arr2: append each element count times
    for num in arr2:
        if num in count:
            result.extend([num] * count[num])
            # Remove the element from the count dictionary
            del count[num]

    # Process remaining numbers: sort them in ascending order and append
    remaining = []
    for num, freq in count.items():
        remaining.extend([num] * freq)
    result.extend(sorted(remaining))

    return result

# Example usage:
print(relativeSortArray([2,3,1,3,2,4,6,7,9,2,19], [2,1,4,3,9,6]))
← Back to All Questions