💬 Discord
Sign In
NeetCode #94LC-1122EasyArrays & Hashing
← Back to All Problems

#94 · #1122 · Relative Sort Array(数组的相对排序)

📌 Problem Statement & Constraints

Given two arrays arr1 and arr2, sort arr1 such that the relative order of elements follows arr2: elements appearing in arr2 come first in arr2's order, and the remaining elements follow in ascending order. Constraints: 1 <= arr1.length, arr2.length <= 1000, 0 <= arr1[i], arr2[i] <= 1000; arr2 has distinct elements.

💡 Core Algorithmic Approaches

  1. Count the occurrences of each value in arr1.
  2. Emit the elements in arr2's order, appending each value as many times as it occurs.
  3. Then emit the remaining values in ascending order by iterating the counter's keys in sorted order.
  4. Setting the count to zero after emitting avoids a second bookkeeping pass over arr2.

💻 Benchmark Python3 Implementation

class Solution:
    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:
        from collections import Counter
        cnt = Counter(arr1)
        res = []
        for x in arr2:
            res.extend([x] * cnt[x])       # all copies, in arr2 order
            cnt[x] = 0                     # consumed
        for x in sorted(cnt):
            res.extend([x] * cnt[x])       # leftovers in ascending order
        return res

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n + m + V log V) where V is the number of distinct leftover values. With the bounded value range, a counting-array sort would make the tail O(V).
💾 Space Complexity
O(n) for the result plus O(V) for the counter.

⚠️ Interview Pitfalls & Follow-ups

  • Forgetting to zero out the consumed counts: elements in arr2 would be emitted twice.
  • Sorting arr1 first and then reordering: workable but more steps than the counting approach.
  • Emitting leftovers in counter order rather than sorted order: the leftovers must be ascending.
  • Assuming every element of arr1 appears in arr2: leftovers are explicitly required by the problem.