Relative Sort Array

🎯

Relative Sort Array

easySORT_SEARCHAmazonGoogle

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.

💡 This problem is about sorting an array based on a custom order defined by another array. Beginners often struggle because it combines sorting with mapping and handling elements not in the custom order.

📋

Problem Statement

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

💡

Example

Input"arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6]"

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

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

• arr1 and arr2 are identical → output is arr1 unchanged
• arr1 contains elements not in arr2 → those elements sorted at end
• arr2 contains only one element → arr1 sorted with that element first
• arr1 contains duplicates of elements in arr2 → duplicates grouped together in order

⚠️

Common Mistakes

Not handling elements in arr1 that are not in arr2

Output misses leftover elements or orders them incorrectly

✅ Collect and sort leftover elements separately and append at the end

Using nested loops without marking used elements

Duplicates may be output multiple times or infinite loops in some variants

✅ Track used elements with a boolean array or frequency map

Sorting entire arr1 instead of custom order

Output is sorted but does not respect arr2 order, failing problem requirements

✅ Sort only leftover elements, output arr2 elements in given order

Using hash map but sorting keys inefficiently or forgetting to remove processed keys

Leftover elements may be duplicated or output in wrong order

✅ Remove keys from map after outputting arr2 elements, then sort leftover keys

Assuming input values are small without checking max value

Frequency array approach may cause memory issues or runtime errors

✅ Check max value before frequency array; fallback to hash map if large

🧠

Brute Force (Nested Loops)

💡 This approach exists to build intuition by directly implementing the problem statement without optimization. It helps understand the sorting requirements clearly.

Intuition

For each element in arr2, scan arr1 and collect all matching elements in order. Then append the remaining elements sorted ascending.

Algorithm

1. Initialize an empty result list.
2. For each element in arr2, scan arr1 and append all matching elements to result.
3. Collect elements in arr1 not in arr2 into a separate list.
4. Sort the leftover list and append it to result.
5. Return the result list.

💡 The nested scanning is simple but inefficient; it clearly separates elements by priority and leftover.

</>

Code

def relative_sort_array(arr1, arr2):
    result = []
    used = [False] * len(arr1)
    for val in arr2:
        for i in range(len(arr1)):
            if not used[i] and arr1[i] == val:
                result.append(arr1[i])
                used[i] = True
    leftover = [arr1[i] for i in range(len(arr1)) if not used[i]]
    leftover.sort()
    result.extend(leftover)
    return result

# Driver code
if __name__ == '__main__':
    arr1 = [2,3,1,3,2,4,6,7,9,2,19]
    arr2 = [2,1,4,3,9,6]
    print(relative_sort_array(arr1, arr2))

Line Notes

result = []Initialize list to store final sorted elements

used = [False] * len(arr1)Track which elements of arr1 have been placed

for val in arr2:Iterate over arr2 to enforce custom order

if not used[i] and arr1[i] == val:Select elements matching current arr2 value not yet used

leftover.sort()Sort elements not in arr2 ascending

result.extend(leftover)Append leftover elements at the end

import java.util.*;
public class Solution {
    public static int[] relativeSortArray(int[] arr1, int[] arr2) {
        List<Integer> result = new ArrayList<>();
        boolean[] used = new boolean[arr1.length];
        for (int val : arr2) {
            for (int i = 0; i < arr1.length; i++) {
                if (!used[i] && arr1[i] == val) {
                    result.add(arr1[i]);
                    used[i] = true;
                }
            }
        }
        List<Integer> leftover = new ArrayList<>();
        for (int i = 0; i < arr1.length; i++) {
            if (!used[i]) leftover.add(arr1[i]);
        }
        Collections.sort(leftover);
        result.addAll(leftover);
        int[] resArr = new int[result.size()];
        for (int i = 0; i < result.size(); i++) resArr[i] = result.get(i);
        return resArr;
    }
    public static void main(String[] args) {
        int[] arr1 = {2,3,1,3,2,4,6,7,9,2,19};
        int[] arr2 = {2,1,4,3,9,6};
        System.out.println(Arrays.toString(relativeSortArray(arr1, arr2)));
    }
}

Line Notes

List<Integer> result = new ArrayList<>();Store final sorted elements dynamically

boolean[] used = new boolean[arr1.length];Track used elements to avoid duplicates

for (int val : arr2)Iterate arr2 to enforce custom order

if (!used[i] && arr1[i] == val)Select matching unused elements from arr1

Collections.sort(leftover);Sort leftover elements ascending

result.addAll(leftover);Append leftover elements at the end

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) {
    vector<int> result;
    vector<bool> used(arr1.size(), false);
    for (int val : arr2) {
        for (int i = 0; i < (int)arr1.size(); i++) {
            if (!used[i] && arr1[i] == val) {
                result.push_back(arr1[i]);
                used[i] = true;
            }
        }
    }
    vector<int> leftover;
    for (int i = 0; i < (int)arr1.size(); i++) {
        if (!used[i]) leftover.push_back(arr1[i]);
    }
    sort(leftover.begin(), leftover.end());
    result.insert(result.end(), leftover.begin(), leftover.end());
    return result;
}

int main() {
    vector<int> arr1 = {2,3,1,3,2,4,6,7,9,2,19};
    vector<int> arr2 = {2,1,4,3,9,6};
    vector<int> res = relativeSortArray(arr1, arr2);
    for (int x : res) cout << x << ' ';
    cout << '\n';
    return 0;
}

Line Notes

vector<int> result;Store final sorted elements

vector<bool> used(arr1.size(), false);Track which arr1 elements are placed

for (int val : arr2)Iterate arr2 to enforce custom order

if (!used[i] && arr1[i] == val)Select matching unused elements from arr1

sort(leftover.begin(), leftover.end());Sort leftover elements ascending

result.insert(result.end(), leftover.begin(), leftover.end());Append leftover elements at the end

function relativeSortArray(arr1, arr2) {
    const result = [];
    const used = new Array(arr1.length).fill(false);
    for (const val of arr2) {
        for (let i = 0; i < arr1.length; i++) {
            if (!used[i] && arr1[i] === val) {
                result.push(arr1[i]);
                used[i] = true;
            }
        }
    }
    const leftover = [];
    for (let i = 0; i < arr1.length; i++) {
        if (!used[i]) leftover.push(arr1[i]);
    }
    leftover.sort((a,b) => a - b);
    result.push(...leftover);
    return result;
}

// Test
const arr1 = [2,3,1,3,2,4,6,7,9,2,19];
const arr2 = [2,1,4,3,9,6];
console.log(relativeSortArray(arr1, arr2));

Line Notes

const result = [];Initialize array for final sorted output

const used = new Array(arr1.length).fill(false);Track which elements have been placed

for (const val of arr2)Iterate arr2 to enforce custom order

if (!used[i] && arr1[i] === val)Select matching unused elements from arr1

leftover.sort((a,b) => a - b);Sort leftover elements ascending

result.push(...leftover);Append leftover elements at the end

⏱

Complexity

TimeO(n*m + k log k) where n = arr1.length, m = arr2.length, k = leftover elements

SpaceO(n) for used array and result list

For each element in arr2, we scan arr1 fully (O(n*m)). Leftover sorting costs O(k log k).

💡 For n=1000 and m=100, this means up to 100,000 comparisons plus sorting leftovers, which is slow.

Interview Verdict: TLE on large inputs; useful only to introduce problem and intuition.

This approach is too slow for large inputs but helps understand the problem and correctness before optimizing.

🧠

Better Approach Using Hash Map and Sorting

💡 This approach improves efficiency by counting frequencies and sorting leftovers only once, avoiding repeated scans.

Intuition

Count how many times each element appears in arr1. Output elements in arr2 order using counts, then output leftover elements sorted ascending.

Algorithm

1. Count frequency of each element in arr1 using a hash map.
2. Initialize an empty result list.
3. For each element in arr2, append it frequency times to result and remove from map.
4. Sort remaining keys in map and append their elements frequency times to result.
5. Return the result list.

💡 Counting frequencies avoids repeated scanning; sorting leftovers once is efficient.

</>

Code

def relative_sort_array(arr1, arr2):
    from collections import Counter
    freq = Counter(arr1)
    result = []
    for val in arr2:
        result.extend([val] * freq[val])
        del freq[val]
    leftover = sorted(freq.elements())
    result.extend(leftover)
    return result

# Driver code
if __name__ == '__main__':
    arr1 = [2,3,1,3,2,4,6,7,9,2,19]
    arr2 = [2,1,4,3,9,6]
    print(relative_sort_array(arr1, arr2))

Line Notes

from collections import CounterImport Counter to count frequencies efficiently

freq = Counter(arr1)Count frequency of each element in arr1

for val in arr2:Output elements in arr2 order using frequency

result.extend([val] * freq[val])Append val frequency times to result

del freq[val]Remove processed element from frequency map

leftover = sorted(freq.elements())Sort leftover elements ascending

result.extend(leftover)Append leftover elements at the end

import java.util.*;
public class Solution {
    public static int[] relativeSortArray(int[] arr1, int[] arr2) {
        Map<Integer, Integer> freq = new HashMap<>();
        for (int num : arr1) freq.put(num, freq.getOrDefault(num, 0) + 1);
        List<Integer> result = new ArrayList<>();
        for (int val : arr2) {
            int count = freq.get(val);
            for (int i = 0; i < count; i++) result.add(val);
            freq.remove(val);
        }
        List<Integer> leftover = new ArrayList<>(freq.keySet());
        Collections.sort(leftover);
        for (int val : leftover) {
            int count = freq.get(val);
            for (int i = 0; i < count; i++) result.add(val);
        }
        int[] resArr = new int[result.size()];
        for (int i = 0; i < result.size(); i++) resArr[i] = result.get(i);
        return resArr;
    }
    public static void main(String[] args) {
        int[] arr1 = {2,3,1,3,2,4,6,7,9,2,19};
        int[] arr2 = {2,1,4,3,9,6};
        System.out.println(Arrays.toString(relativeSortArray(arr1, arr2)));
    }
}

Line Notes

Map<Integer, Integer> freq = new HashMap<>();Map to store frequency counts

for (int num : arr1)Count frequency of each element in arr1

for (int val : arr2)Output elements in arr2 order

freq.remove(val);Remove processed elements from map

Collections.sort(leftover);Sort leftover keys ascending

for (int val : leftover)Output leftover elements frequency times

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;

vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) {
    unordered_map<int,int> freq;
    for (int num : arr1) freq[num]++;
    vector<int> result;
    for (int val : arr2) {
        int count = freq[val];
        for (int i = 0; i < count; i++) result.push_back(val);
        freq.erase(val);
    }
    vector<int> leftover;
    for (auto& p : freq) leftover.push_back(p.first);
    sort(leftover.begin(), leftover.end());
    for (int val : leftover) {
        int count = freq[val];
        for (int i = 0; i < count; i++) result.push_back(val);
    }
    return result;
}

int main() {
    vector<int> arr1 = {2,3,1,3,2,4,6,7,9,2,19};
    vector<int> arr2 = {2,1,4,3,9,6};
    vector<int> res = relativeSortArray(arr1, arr2);
    for (int x : res) cout << x << ' ';
    cout << '\n';
    return 0;
}

Line Notes

unordered_map<int,int> freq;Hash map to count frequencies

for (int num : arr1) freq[num]++;Count frequency of each element

for (int val : arr2)Output elements in arr2 order

freq.erase(val);Remove processed elements

sort(leftover.begin(), leftover.end());Sort leftover keys ascending

for (int val : leftover)Output leftover elements frequency times

function relativeSortArray(arr1, arr2) {
    const freq = new Map();
    for (const num of arr1) freq.set(num, (freq.get(num) || 0) + 1);
    const result = [];
    for (const val of arr2) {
        const count = freq.get(val);
        for (let i = 0; i < count; i++) result.push(val);
        freq.delete(val);
    }
    const leftover = Array.from(freq.keys()).sort((a,b) => a - b);
    for (const val of leftover) {
        const count = freq.get(val);
        for (let i = 0; i < count; i++) result.push(val);
    }
    return result;
}

// Test
const arr1 = [2,3,1,3,2,4,6,7,9,2,19];
const arr2 = [2,1,4,3,9,6];
console.log(relativeSortArray(arr1, arr2));

Line Notes

const freq = new Map();Map to store frequency counts

for (const num of arr1)Count frequency of each element

for (const val of arr2)Output elements in arr2 order

freq.delete(val);Remove processed elements

const leftover = Array.from(freq.keys()).sort((a,b) => a - b);Sort leftover keys ascending

for (const val of leftover)Output leftover elements frequency times

⏱

Complexity

TimeO(n + m + k log k) where n = arr1.length, m = arr2.length, k = leftover elements

SpaceO(n) for frequency map and result list

Counting frequencies is O(n), outputting arr2 elements O(m), sorting leftover keys O(k log k).

💡 For n=100000, this approach is efficient enough to run within time limits.

Interview Verdict: Accepted; efficient and practical for interviews.

This approach balances clarity and efficiency, suitable for coding in interviews.

🧠

Optimal Approach Using Counting Sort (Frequency Array)

💡 This approach uses a frequency array to achieve linear time sorting when input values are bounded, making it optimal.

Intuition

Since values are bounded (0 to 10^6), use an array to count frequencies instead of a hash map. Output elements in arr2 order, then output remaining elements in ascending order by scanning frequency array.

Algorithm

1. Create a frequency array of size max_value + 1 initialized to zero.
2. Count frequency of each element in arr1 by incrementing frequency array.
3. Initialize an empty result list.
4. For each element in arr2, append it frequency times to result and set frequency to zero.
5. For all indices in frequency array, append elements frequency times to result in ascending order.
6. Return the result list.

💡 Frequency array allows O(n + max_value) time, avoiding sorting leftover explicitly.

</>

Code

def relative_sort_array(arr1, arr2):
    max_val = max(arr1)
    freq = [0] * (max_val + 1)
    for num in arr1:
        freq[num] += 1
    result = []
    for val in arr2:
        result.extend([val] * freq[val])
        freq[val] = 0
    for val in range(len(freq)):
        if freq[val] > 0:
            result.extend([val] * freq[val])
    return result

# Driver code
if __name__ == '__main__':
    arr1 = [2,3,1,3,2,4,6,7,9,2,19]
    arr2 = [2,1,4,3,9,6]
    print(relative_sort_array(arr1, arr2))

Line Notes

max_val = max(arr1)Find maximum value to size frequency array

freq = [0] * (max_val + 1)Initialize frequency array for all possible values

for num in arr1: freq[num] += 1Count frequency of each element

for val in arr2:Output elements in arr2 order

freq[val] = 0Reset frequency after outputting to avoid duplicates

for val in range(len(freq))Output leftover elements in ascending order

import java.util.*;
public class Solution {
    public static int[] relativeSortArray(int[] arr1, int[] arr2) {
        int maxVal = 0;
        for (int num : arr1) maxVal = Math.max(maxVal, num);
        int[] freq = new int[maxVal + 1];
        for (int num : arr1) freq[num]++;
        List<Integer> result = new ArrayList<>();
        for (int val : arr2) {
            for (int i = 0; i < freq[val]; i++) result.add(val);
            freq[val] = 0;
        }
        for (int val = 0; val < freq.length; val++) {
            for (int i = 0; i < freq[val]; i++) result.add(val);
        }
        int[] resArr = new int[result.size()];
        for (int i = 0; i < result.size(); i++) resArr[i] = result.get(i);
        return resArr;
    }
    public static void main(String[] args) {
        int[] arr1 = {2,3,1,3,2,4,6,7,9,2,19};
        int[] arr2 = {2,1,4,3,9,6};
        System.out.println(Arrays.toString(relativeSortArray(arr1, arr2)));
    }
}

Line Notes

int maxVal = 0;Find maximum value to size frequency array

int[] freq = new int[maxVal + 1];Frequency array for all possible values

for (int num : arr1) freq[num]++;Count frequency of each element

for (int val : arr2)Output elements in arr2 order

freq[val] = 0;Reset frequency after outputting

for (int val = 0; val < freq.length; val++)Output leftover elements ascending

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) {
    int maxVal = *max_element(arr1.begin(), arr1.end());
    vector<int> freq(maxVal + 1, 0);
    for (int num : arr1) freq[num]++;
    vector<int> result;
    for (int val : arr2) {
        for (int i = 0; i < freq[val]; i++) result.push_back(val);
        freq[val] = 0;
    }
    for (int val = 0; val < (int)freq.size(); val++) {
        for (int i = 0; i < freq[val]; i++) result.push_back(val);
    }
    return result;
}

int main() {
    vector<int> arr1 = {2,3,1,3,2,4,6,7,9,2,19};
    vector<int> arr2 = {2,1,4,3,9,6};
    vector<int> res = relativeSortArray(arr1, arr2);
    for (int x : res) cout << x << ' ';
    cout << '\n';
    return 0;
}

Line Notes

int maxVal = *max_element(arr1.begin(), arr1.end());Find maximum value for frequency array size

vector<int> freq(maxVal + 1, 0);Frequency array initialized to zero

for (int num : arr1) freq[num]++;Count frequency of each element

for (int val : arr2)Output elements in arr2 order

freq[val] = 0;Reset frequency after outputting

for (int val = 0; val < (int)freq.size(); val++)Output leftover elements ascending

function relativeSortArray(arr1, arr2) {
    const maxVal = Math.max(...arr1);
    const freq = new Array(maxVal + 1).fill(0);
    for (const num of arr1) freq[num]++;
    const result = [];
    for (const val of arr2) {
        for (let i = 0; i < freq[val]; i++) result.push(val);
        freq[val] = 0;
    }
    for (let val = 0; val < freq.length; val++) {
        for (let i = 0; i < freq[val]; i++) result.push(val);
    }
    return result;
}

// Test
const arr1 = [2,3,1,3,2,4,6,7,9,2,19];
const arr2 = [2,1,4,3,9,6];
console.log(relativeSortArray(arr1, arr2));

Line Notes

const maxVal = Math.max(...arr1);Find maximum value to size frequency array

const freq = new Array(maxVal + 1).fill(0);Initialize frequency array with zeros

for (const num of arr1) freq[num]++;Count frequency of each element

for (const val of arr2)Output elements in arr2 order

freq[val] = 0;Reset frequency after outputting

for (let val = 0; val < freq.length; val++)Output leftover elements ascending

⏱

Complexity

TimeO(n + k) where n = arr1.length, k = max value in arr1

SpaceO(k) for frequency array and O(n) for result

Counting frequencies and outputting is linear in input size plus max value range, no sorting needed.

💡 For n=100000 and max value 10^6, this is still efficient and faster than sorting leftovers.

Interview Verdict: Accepted; optimal for bounded input values.

This is the best approach when input values are bounded and large input size requires linear time.

📊

All Approaches - One-Glance Tradeoffs

💡 Use Approach 2 or 3 in 95% of interviews; Approach 1 is only for initial explanation.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n*m + k log k)	O(n)	No	N/A	Mention only - never code due to inefficiency
2. Frequency Map + Sorting Leftover	O(n + m + k log k)	O(n)	No	N/A	Code this approach for balanced clarity and efficiency
3. Frequency Array (Counting Sort)	O(n + k)	O(k)	No	N/A	Code if input values are bounded and large input size

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Step 1: Clarify problem constraints and input sizes.Step 2: Describe brute force approach to show understanding.Step 3: Explain frequency counting approach to improve efficiency.Step 4: Discuss optimal counting sort approach if input values are bounded.Step 5: Code the chosen approach carefully and test with examples.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 10min → Test: 3min. Total ~20min

What the Interviewer Tests

Interviewer tests your ability to handle custom sorting, frequency counting, and optimization for large inputs.

Common Follow-ups

• What if arr2 contains elements not in arr1? → Ignore or handle gracefully.
• Can you do this in-place? → Discuss tradeoffs and feasibility.
• What if input values are very large? → Use hash map instead of frequency array.
• How to handle stability if arr1 has duplicates? → Frequency counting preserves grouping.

💡 These follow-ups test your adaptability and deeper understanding of constraints and data structures.

🔍

Pattern Recognition

When to Use

1) Need to sort array by custom order, 2) Custom order given by another array, 3) Elements not in custom order sorted normally, 4) Input size large enough to require optimization

Signature Phrases

relative ordering of itemselements that do not appearsort the elements of arr1 such that

NOT This Pattern When

Standard sorting problems without custom order or frequency considerations

Similar Problems

Sort Colors - sorting by fixed categoriesCustom Sort String - mapping characters to custom orderFrequency Sort - sorting by frequency counts

Practice

1. Consider the following code snippet implementing the optimal solution to rearrange an array so no two adjacent elements are equal. What is the output of the function call make_array_beautiful_heap([1,1,2])?

easy

A. []

B. [1, 1, 2]

C. [1, 2, 1]

D. [2, 1, 1]

Solution

1. Step 1: Check max frequency condition

   Frequency counts: 1 -> 2, 2 -> 1; max_freq=2, n=3, (n+1)//2=2, so condition passes.

2. Step 2: Trace heap operations and result construction

   Heap: [(-2,1), (-1,2)] Pop (-2,1): res=[1], prev_count=-1, prev_num=1 Pop (-1,2): res=[1,2], push back (-1,1) since prev_count<0 Pop (-1,1): res=[1,2,1] Return [1,2,1]

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Output matches expected rearrangement with no adjacent duplicates [OK]

Hint: Check max frequency and simulate heap pops [OK]

Common Mistakes:

• Returning original array without rearrangement
• Confusing heap push/pop order

2. 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

3. What is the time complexity of the optimal h-index algorithm that sorts the citations and uses binary search on possible h values, assuming n is the number of papers?

medium

A. O(n log n) dominated by sorting; counting inside binary search is O(n) per iteration but binary search runs O(log n) times

B. O(n log n) due to sorting plus O(log n) binary search with O(n) counting each iteration

C. O(n²) because binary search calls a linear count each time

D. O(n) because binary search reduces search space quickly

Solution

1. Step 1: Analyze sorting step

   Sorting citations takes O(n log n).

2. Step 2: Analyze binary search and counting

   Binary search runs O(log n) times; each iteration counts papers ≥ mid in O(n). Total counting cost is O(n log n).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sorting plus binary search counting yields O(n log n) [OK]

Hint: Sorting dominates; counting inside binary search multiplies log n [OK]

Common Mistakes:

• Thinking counting is O(1)
• Confusing total binary search cost
• Assuming linear time overall

4. 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

5. Suppose the input array can contain negative integers and duplicates, and you want to find the maximum gap between successive unique elements in sorted order. Which modification to the bucket sort / pigeonhole approach correctly handles this scenario without sorting the entire array explicitly?

hard

A. Sort the array fully to handle negatives and duplicates, then scan for maximum gap.

B. Use buckets sized to cover only positive numbers and skip negatives during bucketing.

C. Ignore duplicates by using a set before bucketing, then apply the standard bucket approach on unique values.

D. Modify bucket size to be the difference between max and min ignoring duplicates, but keep duplicates in buckets.

Solution

1. Step 1: Handle duplicates

   Duplicates do not affect maximum gap between unique elements, so remove duplicates first.

2. Step 2: Apply bucket approach on unique values

   After deduplication, apply pigeonhole principle buckets over full range including negatives.

3. Step 3: Avoid sorting entire array

   This approach avoids full sorting and correctly handles negatives and duplicates.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Deduplication before bucketing preserves correctness [OK]

Hint: Remove duplicates first, then bucket over full range including negatives [OK]

Common Mistakes:

• Ignoring negatives in bucket sizing
• Keeping duplicates causing incorrect gaps
• Sorting entire array defeats bucket approach