Bird
Raised Fist0
Interview Prepsort-and-searcheasyAmazonGoogle

Relative Sort Array

Choose your preparation mode4 modes available
Try ItSolutionTrace
▶
Steps
setup

Find maximum value in arr1

We scan arr1 to find the maximum value, which determines the size of the frequency array.

💡 Knowing the max value lets us create a frequency array that can count all elements efficiently by their value.
Line:max_val = max(arr1)
💡 The frequency array size depends on the largest element in arr1.
📊
Relative Sort Array - Watch the Algorithm Execute, Step by Step
Watching each frequency count and placement step reveals how the algorithm efficiently sorts with a custom order without complex comparisons.
Step 1/20
·Active fill★Answer cell
compare
2
0
3
1
1
2
3
3
2
4
4
5
6
6
7
7
9
8
2
9
max_val
19
10
Result: []
setup
0
0
0
1
0
2
0
3
0
4
0
5
0
6
0
7
0
8
0
9
0
10
0
11
0
12
0
13
0
14
0
15
0
16
0
17
0
18
0
19
Result: []
move_right
i
0
0
0
1
1
2
0
3
0
4
0
5
0
6
0
7
0
8
0
9
0
10
0
11
0
12
0
13
0
14
0
15
0
16
0
17
0
18
0
19
Result: []
move_right
0
0
i
0
1
1
2
1
3
0
4
0
5
0
6
0
7
0
8
0
9
0
10
0
11
0
12
0
13
0
14
0
15
0
16
0
17
0
18
0
19
Result: []
move_right
0
0
1
1
i
1
2
1
3
0
4
0
5
0
6
0
7
0
8
0
9
0
10
0
11
0
12
0
13
0
14
0
15
0
16
0
17
0
18
0
19
Result: []
move_right
0
0
1
1
1
2
i
2
3
0
4
0
5
0
6
0
7
0
8
0
9
0
10
0
11
0
12
0
13
0
14
0
15
0
16
0
17
0
18
0
19
Result: []
move_right
0
0
1
1
2
2
2
3
i
0
4
0
5
0
6
0
7
0
8
0
9
0
10
0
11
0
12
0
13
0
14
0
15
0
16
0
17
0
18
0
19
Result: []
move_right
0
0
1
1
2
2
2
3
1
4
i
0
5
0
6
0
7
0
8
0
9
0
10
0
11
0
12
0
13
0
14
0
15
0
16
0
17
0
18
0
19
Result: []
move_right
0
0
1
1
2
2
2
3
1
4
0
5
i
1
6
0
7
0
8
0
9
0
10
0
11
0
12
0
13
0
14
0
15
0
16
0
17
0
18
0
19
Result: []
move_right
0
0
1
1
2
2
2
3
1
4
0
5
1
6
i
1
7
0
8
0
9
0
10
0
11
0
12
0
13
0
14
0
15
0
16
0
17
0
18
0
19
Result: []
move_right
0
0
1
1
2
2
2
3
1
4
0
5
1
6
1
7
i
0
8
1
9
0
10
0
11
0
12
0
13
0
14
0
15
0
16
0
17
0
18
0
19
Result: []
move_right
0
0
1
1
3
2
2
3
1
4
0
5
1
6
1
7
0
8
i
1
9
0
10
0
11
0
12
0
13
0
14
0
15
0
16
0
17
0
18
0
19
Result: []
move_right
0
0
1
1
3
2
2
3
1
4
0
5
1
6
1
7
0
8
1
9
i
0
10
0
11
0
12
0
13
0
14
0
15
0
16
0
17
0
18
1
19
Result: []
record
j
0
0
1
1
0
2
2
3
1
4
0
5
1
6
1
7
0
8
1
9
0
10
0
11
0
12
0
13
0
14
0
15
0
16
0
17
0
18
1
19
Result: [2,2,2]
record
0
0
j
0
1
0
2
2
3
1
4
0
5
1
6
1
7
0
8
1
9
0
10
0
11
0
12
0
13
0
14
0
15
0
16
0
17
0
18
1
19
Result: [2,2,2,1]
record
0
0
0
1
j
0
2
2
3
0
4
0
5
1
6
1
7
0
8
1
9
0
10
0
11
0
12
0
13
0
14
0
15
0
16
0
17
0
18
1
19
Result: [2,2,2,1,4]
record
0
0
0
1
0
2
j
0
3
0
4
0
5
1
6
1
7
0
8
1
9
0
10
0
11
0
12
0
13
0
14
0
15
0
16
0
17
0
18
1
19
Result: [2,2,2,1,4,3,3]
record
0
0
0
1
0
2
0
3
j
0
4
0
5
1
6
1
7
0
8
0
9
0
10
0
11
0
12
0
13
0
14
0
15
0
16
0
17
0
18
1
19
Result: [2,2,2,1,4,3,3,9]
record
0
0
0
1
0
2
0
3
0
4
j
0
5
0
6
1
7
0
8
0
9
0
10
0
11
0
12
0
13
0
14
0
15
0
16
0
17
0
18
1
19
Result: [2,2,2,1,4,3,3,9,6]
record
0
0
0
1
0
2
0
3
0
4
0
5
0
6
val
0
7
0
8
0
9
0
10
0
11
0
12
0
13
0
14
0
15
0
16
0
17
0
18
0
19
Result: [2,2,2,1,4,3,3,9,6,7,19]

Key Takeaways

✓ Frequency array enables O(n) counting of elements by value, avoiding complex comparisons.

This insight is hard to see from code alone because the frequency array abstracts counting away from sorting logic.

✓ Appending elements in arr2 order first ensures custom priority sorting before appending leftovers.

Visualizing this order clarifies how the algorithm respects the custom order without sorting arr1 directly.

✓ Remaining elements are appended in ascending order by iterating frequency array indices.

Seeing leftover elements appended last shows how the algorithm handles elements not in arr2 cleanly.

Practice

(1/5)
1. Given the following Python code for finding missing ranges, what is the final output when calling find_missing_ranges([0, 1, 3, 50, 75], 0, 99)?
easy
A. ['2', '4->49', '51->74', '76->99']
B. ['2', '4->49', '51->74', '76->98', '99']
C. ['2', '4->49', '51->74', '76->99']
D. ['2', '4->49', '51->74', '75->99']

Solution

  1. Step 1: Trace pointer and bisect calls

    Start pointer=0, bisect finds 0 at idx=0, pointer updated to 1+1=2. At pointer=2, bisect finds idx=2 with curr=3, missing range 2 (single number) added. Pointer updated to 3+1=4. At pointer=4, bisect finds idx=3 with curr=50, missing range 4->49 added. Pointer updated to 50+1=51. At pointer=51, bisect finds idx=4 with curr=75, missing range 51->74 added. Pointer updated to 75+1=76. At pointer=76, bisect idx=5 (end), missing range 76->99 added. Loop ends.

  2. Step 2: Confirm final missing ranges list

    Missing ranges: ['2', '4->49', '51->74', '76->99']

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    All gaps between nums and bounds correctly identified [OK]
Hint: Check pointer updates and bisect indices carefully [OK]
Common Mistakes:
  • Off-by-one errors in range ends
  • Including last number incorrectly
  • Misformatting single number ranges
2. The following code attempts to find the minimum absolute difference but contains a subtle bug. Which line causes incorrect results? 
def minimum_abs_difference(arr):
    min_diff = float('inf')
    for i in range(len(arr) - 1):
        diff = arr[i + 1] - arr[i]
        if diff < min_diff:
            min_diff = diff
    arr.sort()
    return min_diff
medium
A. Line 2: initializing min_diff before sorting
B. Line 6: sorting after scanning pairs
C. Line 7: returning min_diff without recomputing
D. Line 3: iterating without sorting first

Solution

  1. Step 1: Identify order of operations

    The array is scanned for differences before sorting, so adjacent pairs are not guaranteed to be closest.

  2. Step 2: Pinpoint the bug

    Line 3 iterates over unsorted array, causing incorrect min_diff.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Sorting must happen before scanning adjacent pairs [OK]
Hint: Must sort before scanning adjacent pairs [OK]
Common Mistakes:
  • Sorting after scanning
  • Not updating min_diff correctly
3. What is the time and space complexity of the optimal one-pass Dutch National Flag algorithm for sorting colors in an array of length n?
medium
A. Time: O(n log n), Space: O(1) due to in-place swaps
B. Time: O(n^2), Space: O(1) due to nested pointer updates
C. Time: O(n), Space: O(n) because it uses extra arrays for counting
D. Time: O(n), Space: O(1) because it scans array once with constant pointers

Solution

  1. Step 1: Identify time complexity of outer loop

    The algorithm uses a single while loop with mid pointer moving forward, scanning each element at most once, so O(n).

  2. Step 2: Identify space complexity

    Only three pointers (low, mid, high) are used, no extra arrays or recursion, so O(1) space.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Single pass with constant pointers -> O(n) time and O(1) space [OK]
Hint: One pass with constant pointers means O(n) time and O(1) space [OK]
Common Mistakes:
  • Confusing counting sort space with Dutch Flag space
  • Assuming nested loops cause O(n^2) time
  • Thinking swaps add extra space
4. Suppose the problem is modified so that elements can be reused unlimited times to form an infinitely long array with no two adjacent elements equal. Which modification to the heap-based algorithm correctly handles this variant?
hard
A. Remove the max frequency check and keep pushing elements back with updated counts indefinitely.
B. Use a queue instead of a heap to cycle through elements ensuring no two adjacent are equal.
C. Use a max heap but reset counts to original frequencies after each full pass through the heap.
D. Modify the algorithm to never decrement counts and always push elements back to allow infinite reuse.

Solution

  1. Step 1: Understand infinite reuse implication

    Since elements can be reused unlimited times, counts do not decrease; the algorithm must allow repeated placement without decrementing counts.

  2. Step 2: Modify heap usage accordingly

    Never decrement counts and always push elements back to heap to maintain availability, ensuring no two adjacent elements are equal.

  3. Step 3: Evaluate other options

    Removing max frequency check or resetting counts breaks correctness or efficiency; queue does not prioritize frequency.

  4. Final Answer:

    Option D -> Option D

  5. Quick Check:

    Maintaining counts without decrement allows infinite reuse without adjacency violation [OK]
Hint: Infinite reuse means counts stay constant [OK]
Common Mistakes:
  • Removing checks without adjusting counts
  • Resetting counts causing incorrect order
5. Suppose the problem changes: now you must sort each diagonal but allow elements to be reused multiple times (i.e., duplicates can be placed anywhere along the diagonal). Which modification to the algorithm correctly handles this variant efficiently?
hard
A. Sort each diagonal once and store sorted arrays; assign elements from these arrays repeatedly as needed.
B. Use counting sort per diagonal to handle duplicates efficiently and assign elements accordingly.
C. Use the same min-heap approach but skip popping elements to allow reuse.
D. Apply dynamic programming to track reuse counts and reconstruct diagonals with duplicates.

Solution

  1. Step 1: Recognize reuse implies duplicates can appear multiple times

    Min-heaps popping elements once won't allow reuse; we need a method that counts frequencies.

  2. Step 2: Use counting sort per diagonal

    Counting sort efficiently handles duplicates by frequency counts, allowing reuse without repeated heap operations.

  3. Step 3: Assign elements back using frequency counts

    Reconstruct diagonals by placing elements according to counts, supporting reuse efficiently.

  4. Final Answer:

    Option B -> Option B

  5. Quick Check:

    Counting sort suits duplicates and reuse better than heap popping [OK]
Hint: Counting sort handles duplicates and reuse efficiently [OK]
Common Mistakes:
  • Trying to reuse popped heap elements
  • Re-sorting entire matrix repeatedly
  • Using DP unnecessarily complicates solution
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard