Relative Sort Array

📋

Problem

Imagine you have a list of products to display on a website, but you want to show some featured products first in a specific order, and then the rest sorted normally.

Given two arrays arr1 and arr2, the elements of arr2 are distinct, and all elements in arr2 appear in arr1. Sort the elements of arr1 such that the relative ordering of items in arr1 are the same as in arr2. Elements that do not appear in arr2 should be placed at the end of arr1 in ascending order. Input: Two integer arrays arr1 and arr2. Output: The sorted arr1 according to the relative order defined by arr2.

1 ≤ arr1.length, arr2.length ≤ 10^50 ≤ arr1[i], arr2[i] ≤ 10^6All elements in arr2 are distinctAll elements in arr2 appear in arr1

Edge cases: arr1 and arr2 are identical → output is arr1 unchangedarr1 contains elements not in arr2 → those elements sorted at endarr2 contains only one element → arr1 sorted with that element first

</>

IDE

def relative_sort_array(arr1: list[int], arr2: list[int]) -> list[int]:public int[] relativeSortArray(int[] arr1, int[] arr2)vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2)function relativeSortArray(arr1, arr2)

def relative_sort_array(arr1, arr2):
    # Write your solution here
    pass

class Solution {
    public int[] relativeSortArray(int[] arr1, int[] arr2) {
        // Write your solution here
        return new int[0];
    }
}

#include <vector>
using namespace std;

vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) {
    // Write your solution here
    return {};
}

function relativeSortArray(arr1, arr2) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: [1,2,3,4,5,6]Sorting entire arr1 ascending ignoring arr2 order.✅ Use frequency map to output arr2 elements in given order first, then sort leftovers ascending.

Wrong: [2,3,1,4,5]Outputting only one occurrence per arr2 element instead of all duplicates.✅ Count frequencies of arr1 elements and output all duplicates of arr2 elements before leftovers.

Wrong: [7,8,9,10]Sorting arr2 elements ascending instead of outputting in arr2 order.✅ Output arr2 elements in the exact order given using frequency map.

Wrong: Timeout or no outputUsing nested loops for matching arr2 elements causing O(n*m) complexity.✅ Use frequency map or counting sort to achieve O(n + m + k log k) or better.

Wrong: Error or crashNo handling of empty input arrays causing index errors.✅ Add checks for empty arr1 and arr2 and return empty list if arr1 is empty.

✓

Test Cases

Try testing your code with empty and single-element arrays to catch base case bugs.

Consider tricky cases where duplicates and order matter; avoid greedy traps.

Focus on algorithmic complexity; nested loops will time out on large inputs.

t1_01basic

Input{"arr1":[2,3,1,3,2,4,6,7,9,2,19],"arr2":[2,1,4,3,9,6]}

Expected[2,2,2,1,4,3,3,9,6,7,19]

⏱ Performance - must finish in 2000ms

Elements in arr2 appear first in the order given, then remaining elements 7 and 19 are sorted ascending at the end.

💡 Focus on sorting arr1 to match the order of arr2 first, then sort leftovers.

💡 Use a frequency map for arr1 elements and output in arr2 order, then sort remaining keys.

💡 Build a frequency dictionary, output elements in arr2 order using frequencies, then append sorted leftovers.

Why it failed: Output order incorrect: likely missed grouping arr1 elements by arr2 order or sorting leftovers ascending. Fix by using frequency map and outputting in arr2 order first, then sorted leftovers.

✓ Correctly orders arr1 elements by arr2 and sorts leftovers ascending.

t1_02basic

Input{"arr1":[5,17,100,11,5,17,5,11],"arr2":[17,5]}

Expected[17,17,5,5,5,11,11,100]

⏱ Performance - must finish in 2000ms

Elements 17 and 5 appear first in arr2 order with duplicates grouped, then remaining elements 11 and 100 sorted ascending at the end.

💡 Group arr1 elements by arr2 order first, then sort remaining elements ascending.

💡 Count frequencies of arr1 elements, output arr2 elements by frequency, then sort and append leftovers.

💡 Use a frequency map, output all 17s then 5s, then append sorted [11,11,100].

Why it failed: Incorrect grouping or leftover sorting: likely outputting leftovers before arr2 elements or not grouping duplicates. Fix by outputting arr2 elements first using frequency map, then sorted leftovers.

✓ Correctly groups duplicates and sorts leftovers after arr2 elements.

t2_01edge

Input{"arr1":[],"arr2":[]}

Expected[]

⏱ Performance - must finish in 2000ms

Empty input arrays produce empty output.

💡 Check behavior when input arrays are empty.

💡 Ensure code handles zero-length arrays without errors.

💡 Return empty list immediately if arr1 is empty.

Why it failed: Fails on empty input: likely no check for empty arrays causing errors or wrong output. Fix by returning empty list if arr1 is empty.

✓ Handles empty input arrays correctly.

t2_02edge

Input{"arr1":[10],"arr2":[10]}

Expected[10]

⏱ Performance - must finish in 2000ms

Single element arrays identical produce same output.

💡 Test with single element arrays where arr1 equals arr2.

💡 Ensure single element is returned unchanged.

💡 Return arr1 as is if arr1 and arr2 contain the same single element.

Why it failed: Fails single element case: likely mishandles single element or frequency counting. Fix by correctly handling single element frequency and output.

✓ Correctly handles single element identical arrays.

t2_03edge

Input{"arr1":[3,3,3,3],"arr2":[3]}

Expected[3,3,3,3]

⏱ Performance - must finish in 2000ms

All elements identical and in arr2 produce unchanged output.

💡 Test when all arr1 elements are the same and appear in arr2.

💡 Ensure duplicates are grouped and output correctly.

💡 Output all occurrences of the single arr2 element in arr1.

Why it failed: Fails identical duplicates: likely missing grouping duplicates or frequency counting. Fix by counting all duplicates and outputting them in order.

✓ Correctly outputs all duplicates of arr2 elements.

t3_01corner

Input{"arr1":[5,3,1,2,4,6],"arr2":[1,2,3]}

Expected[1,2,3,4,5,6]

⏱ Performance - must finish in 2000ms

Greedy approach fails if sorting leftovers incorrectly; leftovers must be sorted ascending after arr2 elements.

💡 Beware of greedy sorting leftovers before processing arr2 order.

💡 Check that leftovers are sorted ascending after outputting arr2 elements.

💡 Use frequency map to output arr2 elements first, then sort and append leftovers.

Why it failed: Greedy trap: sorting entire arr1 ignoring arr2 order or sorting leftovers before arr2 elements. Fix by outputting arr2 elements first using frequency map, then sorted leftovers.

✓ Correctly separates arr2 order and leftover sorting.

t3_02corner

Input{"arr1":[2,2,2,3,3,1,1,4,4,5],"arr2":[2,3,1]}

Expected[2,2,2,3,3,1,1,4,4,5]

⏱ Performance - must finish in 2000ms

Confusing 0/1 vs unbounded: duplicates of arr2 elements must be grouped, not just one occurrence each.

💡 Check that all duplicates of arr2 elements are included, not just one.

💡 Use frequency map to count all occurrences, not a set.

💡 Output each arr2 element repeated frequency times before leftovers.

Why it failed: 0/1 confusion: outputting only one occurrence per arr2 element instead of all duplicates. Fix by counting frequencies and outputting all duplicates.

✓ Correctly outputs all duplicates of arr2 elements.

t3_03corner

Input{"arr1":[7,8,9,10],"arr2":[10,9,8,7]}

Expected[10,9,8,7]

⏱ Performance - must finish in 2000ms

Reverse order arr2 requires output in exact arr2 order, not ascending.

💡 Do not sort arr2 elements ascending; output in arr2 order exactly.

💡 Use arr2 as a key order, not a sorting key.

💡 Output arr2 elements in given order, then leftovers sorted ascending if any.

Why it failed: Sorting arr2 elements ascending instead of outputting in arr2 order. Fix by outputting arr2 elements in given order using frequency map.

✓ Correctly outputs arr2 elements in given order.

t4_01performance

Input{"_description":"n=100000 at constraint boundary - executor generates this input"}

Expectednull

⏱ Performance - must finish in 2000ms

Large input with n=100000 tests O(n + m + k log k) or better complexity within 2 seconds.

💡 Use frequency map or counting sort to achieve linear or near-linear time.

💡 Avoid nested loops or sorting entire arr1 without grouping.

💡 Precompute frequencies and output in arr2 order, then sort leftovers efficiently.

Why it failed: TLE due to nested loops or sorting entire arr1 repeatedly. Fix by using frequency map and sorting only leftovers once.

✓ Algorithm runs within time limit using efficient frequency counting and sorting.

Practice

1. Consider the following Python function to find the minimum absolute difference in an array. What is the returned value when the input is [4, 2, 1, 3]?

def minimum_abs_difference(arr):
    arr.sort()
    min_diff = float('inf')
    for i in range(len(arr) - 1):
        diff = arr[i + 1] - arr[i]
        if diff == 1:
            return 1
        if diff < min_diff:
            min_diff = diff
    return min_diff

print(minimum_abs_difference([4, 2, 1, 3]))

easy

A. 1

B. 3

C. 2

D. 0

Solution

1. Step 1: Sort the array

   Sorted array is [1, 2, 3, 4].

2. Step 2: Iterate and check adjacent differences

   Differences: 2-1=1 -> triggers early return 1.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Early exit on diff==1 returns 1 [OK]

Hint: Early exit returns 1 on first adjacent difference of 1 [OK]

Common Mistakes:

• Forgetting early exit
• Returning difference between non-adjacent pairs

2. What is the time complexity of the optimal bucket sort based solution for finding the minimum time difference among n time points, where each time is in "HH:MM" format?

medium

A. O(n + 1440) because we mark seen times and scan a fixed-size array

B. O(n log n) due to sorting the input times

C. O(n^2) because we compare all pairs of times

D. O(1440^2) since we scan all possible time pairs in the fixed range

Solution

1. Step 1: Mark times in a fixed-size boolean array

   Marking each of the n times in a 1440-length array is O(n).

2. Step 2: Scan the fixed 1440-length array once

   Scanning the array to find minimum difference is O(1440), which is constant and independent of n.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Overall complexity is O(n + 1440) -> O(n) for large n [OK]

Hint: Fixed 1440 array makes scanning O(1) relative to n [OK]

Common Mistakes:

• Assuming sorting is needed -> O(n log n)
• Confusing nested loops -> O(n^2)
• Thinking scanning pairs in fixed array is quadratic

3. The following code attempts to sort a matrix diagonally using min-heaps keyed by (row - col). Identify the line containing the subtle bug that causes incorrect sorting or corrupted output.

from typing import List
import collections
import heapq

def diagonalSort(mat: List[List[int]]) -> List[List[int]]:
    m, n = len(mat), len(mat[0])
    diagonals = collections.defaultdict(list)
    for i in range(m):
        for j in range(n):
            heapq.heappush(diagonals[i + j], mat[i][j])  # Line X
    for i in range(m):
        for j in range(n):
            mat[i][j] = heapq.heappop(diagonals[i - j])  # Line Y
    return mat

medium

A. Line X: Using i + j as diagonal key instead of i - j.

B. Line Y: Popping from diagonals keyed by i - j instead of i + j.

C. Line X: Using heapq.heappush instead of sorting the diagonal list first.

D. Line Y: Assigning popped element directly without checking if heap is empty.

Solution

1. Step 1: Check diagonal key consistency

   The diagonal key must be consistent for both pushing and popping. Here, push uses i + j, pop uses i - j, causing mismatch.

2. Step 2: Identify impact of key mismatch

   Elements pushed into one diagonal heap are popped from a different key, leading to empty heaps or incorrect elements assigned.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Diagonal keys must match exactly for correct sorting [OK]

Hint: Diagonal key must be consistent for push and pop [OK]

Common Mistakes:

• Mixing i + j and i - j keys
• Forgetting to check heap emptiness
• Using reverse sorting but popping incorrectly

4. Suppose the citation counts can be negative or zero, and you want to compute the h-index considering only non-negative citations. Which modification to the optimal algorithm is correct?

hard

A. Filter out negative citations before sorting, then apply the same binary search algorithm on the filtered list.

B. Keep all citations including negatives, but treat negative values as zero during counting.

C. Use the brute force approach to handle negative values correctly without filtering.

D. Sort citations ascending and perform binary search on h values including negatives.

Solution

1. Step 1: Understand problem with negatives

   Negative citations do not contribute to h-index; they should be excluded.

2. Step 2: Modify input before algorithm

   Filter out negatives, then sort descending and apply binary search as usual.

3. Step 3: Why other options fail

   Treating negatives as zero inflates counts incorrectly; brute force is inefficient; ascending sort breaks counting logic.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Filtering negatives preserves correctness and efficiency [OK]

Hint: Exclude negatives before sorting and searching [OK]

Common Mistakes:

• Counting negatives as zero
• Not filtering negatives
• Sorting ascending

5. Suppose the input array can contain duplicate elements and negative numbers. Which modification to the optimal approach ensures correct minimum absolute difference calculation?

hard

A. Sort the array and scan adjacent pairs, but use absolute difference instead of subtraction.

B. Sort the array and scan adjacent pairs using subtraction as is, since sorting orders negatives correctly.

C. Use nested loops to compare all pairs because sorting fails with negatives.

D. Ignore duplicates and negatives since they don't affect minimum difference.

Solution

1. Step 1: Understand sorting with negatives

   Sorting places negative numbers in ascending order correctly.

2. Step 2: Adjacent subtraction works for minimum difference

   Difference between adjacent sorted elements is always non-negative or zero; no need for absolute value.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Sorting handles negatives; subtraction suffices [OK]

Hint: Sorting handles negatives; no abs needed on adjacent pairs [OK]

Common Mistakes:

• Using abs unnecessarily
• Thinking sorting fails with negatives