Find K-th Smallest Pair Distance

🎯

Find K-th Smallest Pair Distance

hardHEAPGoogleAmazon

Imagine you have a list of houses along a street and want to find the K-th smallest distance between any two houses to decide where to build a new facility.

💡 This problem asks for the K-th smallest difference between pairs in an array. Beginners often struggle because the naive approach is too slow and the problem requires a clever use of binary search on the answer space combined with counting pairs efficiently.

📋

Problem Statement

Given an integer array nums and an integer k, return the k-th smallest distance among all the pairs (nums[i], nums[j]) where i < j. The distance of a pair (A, B) is defined as the absolute difference between A and B.

1 ≤ nums.length ≤ 10^50 ≤ nums[i] ≤ 10^61 ≤ k ≤ nums.length * (nums.length - 1) / 2

💡

Example

Input"nums = [1,3,1], k = 1"

Output0

All pairs are (1,3) distance 2, (1,1) distance 0, (3,1) distance 2. The 1st smallest distance is 0.

Input"nums = [1,6,1], k = 3"

Output5

Pairs: (1,6)=5, (1,1)=0, (6,1)=5. Sorted distances: 0,5,5. The 3rd smallest is 5.

• All elements are the same → output should be 0
• k equals 1 → smallest pair distance
• k equals maximum pairs → largest pair distance
• Array with two elements → only one pair

⚠️

Common Mistakes

Not sorting the array before counting pairs

Two-pointer counting fails or gives incorrect counts

✅ Always sort the array before counting pairs

Using linear search instead of binary search on answer space

Solution becomes too slow and times out

✅ Use binary search between 0 and max distance

Incorrectly counting pairs with distance ≤ mid (off-by-one errors)

Wrong count leads to incorrect binary search adjustments

✅ Carefully implement two-pointer counting ensuring all pairs ≤ mid are counted

Not handling duplicates properly

Incorrect pair counts or wrong final answer

✅ Sorting and two-pointer counting naturally handle duplicates; ensure no assumptions break

Using a max-heap instead of min-heap in heap approach

Cannot get smallest pair distances first, breaking logic

✅ Use a min-heap to always pop the smallest distance pair

🧠

Brute Force (Nested Loops)

💡 This approach exists to build intuition by directly computing all pair distances. It is simple but inefficient, helping beginners understand the problem's core before optimizing.

Intuition

Calculate the distance for every pair and sort all distances to find the k-th smallest.

Algorithm

1. Initialize an empty list to store all pair distances.
2. Use two nested loops to generate all pairs (i, j) with i < j.
3. Calculate the absolute difference for each pair and add it to the list.
4. Sort the list of distances and return the element at index k-1.

💡 The nested loops and sorting are easy to understand but lead to high time complexity, which is the main challenge.

</>

Code

def smallestDistancePair(nums, k):
    distances = []
    n = len(nums)
    for i in range(n):
        for j in range(i+1, n):
            distances.append(abs(nums[i] - nums[j]))
    distances.sort()
    return distances[k-1]

# Driver code
if __name__ == '__main__':
    print(smallestDistancePair([1,3,1], 1))  # Output: 0

Line Notes

distances = []Initialize list to store all pair distances

for i in range(n)Outer loop to pick first element of pair

for j in range(i+1, n)Inner loop to pick second element ensuring i < j

distances.append(abs(nums[i] - nums[j]))Calculate and store absolute difference

distances.sort()Sort all distances to find k-th smallest

return distances[k-1]Return the k-th smallest distance (1-based index)

import java.util.*;
public class Solution {
    public int smallestDistancePair(int[] nums, int k) {
        List<Integer> distances = new ArrayList<>();
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                distances.add(Math.abs(nums[i] - nums[j]));
            }
        }
        Collections.sort(distances);
        return distances.get(k - 1);
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.smallestDistancePair(new int[]{1,3,1}, 1)); // Output: 0
    }
}

Line Notes

List<Integer> distances = new ArrayList<>()Create list to hold all pair distances

for (int i = 0; i < n; i++)Outer loop selects first element

for (int j = i + 1; j < n; j++)Inner loop selects second element ensuring i < j

distances.add(Math.abs(nums[i] - nums[j]))Calculate and add absolute difference

Collections.sort(distances)Sort distances to find k-th smallest

return distances.get(k - 1)Return the k-th smallest distance

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

int smallestDistancePair(vector<int>& nums, int k) {
    vector<int> distances;
    int n = nums.size();
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            distances.push_back(abs(nums[i] - nums[j]));
        }
    }
    sort(distances.begin(), distances.end());
    return distances[k - 1];
}

int main() {
    vector<int> nums = {1,3,1};
    cout << smallestDistancePair(nums, 1) << endl; // Output: 0
    return 0;
}

Line Notes

vector<int> distances;Vector to store all pair distances

for (int i = 0; i < n; i++)Outer loop picks first element

for (int j = i + 1; j < n; j++)Inner loop picks second element ensuring i < j

distances.push_back(abs(nums[i] - nums[j]))Calculate and store absolute difference

sort(distances.begin(), distances.end())Sort distances to find k-th smallest

return distances[k - 1];Return the k-th smallest distance

function smallestDistancePair(nums, k) {
    const distances = [];
    const n = nums.length;
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            distances.push(Math.abs(nums[i] - nums[j]));
        }
    }
    distances.sort((a, b) => a - b);
    return distances[k - 1];
}

// Test
console.log(smallestDistancePair([1,3,1], 1)); // Output: 0

Line Notes

const distances = []Initialize array to hold all pair distances

for (let i = 0; i < n; i++)Outer loop selects first element

for (let j = i + 1; j < n; j++)Inner loop selects second element ensuring i < j

distances.push(Math.abs(nums[i] - nums[j]))Calculate and store absolute difference

distances.sort((a, b) => a - b)Sort distances numerically to find k-th smallest

return distances[k - 1]Return the k-th smallest distance

⏱

Complexity

TimeO(n^2 log (n^2)) = O(n^2 log n)

SpaceO(n^2)

We generate all pairs (n*(n-1)/2 ~ n^2), then sort them which takes O(n^2 log n^2) time.

💡 For n=1000, this means about 1 million pairs and sorting them, which is too slow for large inputs.

Interview Verdict: TLE

This approach times out on large inputs but is useful to understand the problem and correctness before optimizing.

🧠

Sorting + Binary Search on Answer + Two Pointers

💡 This approach introduces a powerful technique: binary searching the answer space combined with counting pairs efficiently, which is a common pattern in hard selection problems.

Intuition

Sort the array, then binary search the distance d. For each d, count how many pairs have distance ≤ d using two pointers. Narrow down d until the k-th smallest distance is found.

Algorithm

1. Sort the input array nums.
2. Set low = 0 and high = max(nums) - min(nums) as the search range for distances.
3. While low < high:
4. - Set mid = (low + high) // 2.
5. - Count pairs with distance ≤ mid using two pointers.
6. - If count < k, set low = mid + 1; else set high = mid.
7. Return low as the k-th smallest pair distance.

💡 The key is efficiently counting pairs ≤ mid using two pointers, which avoids enumerating all pairs.

</>

Code

def smallestDistancePair(nums, k):
    nums.sort()
    n = len(nums)
    def count_pairs(mid):
        count = left = 0
        for right in range(n):
            while nums[right] - nums[left] > mid:
                left += 1
            count += right - left
        return count

    low, high = 0, nums[-1] - nums[0]
    while low < high:
        mid = (low + high) // 2
        if count_pairs(mid) < k:
            low = mid + 1
        else:
            high = mid
    return low

# Driver code
if __name__ == '__main__':
    print(smallestDistancePair([1,3,1], 1))  # Output: 0

Line Notes

nums.sort()Sort array to enable two-pointer counting

def count_pairs(mid):Helper counts pairs with distance ≤ mid

while nums[right] - nums[left] > mid:Move left pointer to maintain distance ≤ mid

count += right - leftAdd number of valid pairs ending at right

low, high = 0, nums[-1] - nums[0]Initialize binary search range for distances

if count_pairs(mid) < k:If fewer pairs than k, increase distance

else: high = midOtherwise, try smaller distance

return lowLow converges to k-th smallest distance

import java.util.*;
public class Solution {
    public int smallestDistancePair(int[] nums, int k) {
        Arrays.sort(nums);
        int n = nums.length;
        int low = 0, high = nums[n - 1] - nums[0];

        while (low < high) {
            int mid = (low + high) / 2;
            int count = 0, left = 0;
            for (int right = 0; right < n; right++) {
                while (nums[right] - nums[left] > mid) {
                    left++;
                }
                count += right - left;
            }
            if (count < k) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return low;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.smallestDistancePair(new int[]{1,3,1}, 1)); // Output: 0
    }
}

Line Notes

Arrays.sort(nums)Sort array for two-pointer counting

int low = 0, high = nums[n - 1] - nums[0]Set binary search range for distances

while (low < high)Binary search loop to narrow distance

while (nums[right] - nums[left] > mid)Adjust left pointer to maintain distance ≤ mid

count += right - leftCount valid pairs ending at right

if (count < k)If fewer pairs than k, increase low

else high = midOtherwise, decrease high

return lowReturn k-th smallest distance

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

int countPairs(const vector<int>& nums, int mid) {
    int count = 0, left = 0;
    for (int right = 0; right < (int)nums.size(); right++) {
        while (nums[right] - nums[left] > mid) {
            left++;
        }
        count += right - left;
    }
    return count;
}

int smallestDistancePair(vector<int>& nums, int k) {
    sort(nums.begin(), nums.end());
    int low = 0, high = nums.back() - nums.front();
    while (low < high) {
        int mid = low + (high - low) / 2;
        if (countPairs(nums, mid) < k) {
            low = mid + 1;
        } else {
            high = mid;
        }
    }
    return low;
}

int main() {
    vector<int> nums = {1,3,1};
    cout << smallestDistancePair(nums, 1) << endl; // Output: 0
    return 0;
}

Line Notes

sort(nums.begin(), nums.end())Sort array for two-pointer counting

int low = 0, high = nums.back() - nums.front()Initialize binary search range

while (low < high)Binary search loop to find distance

while (nums[right] - nums[left] > mid)Move left pointer to keep distance ≤ mid

count += right - leftCount pairs with distance ≤ mid

if (countPairs(nums, mid) < k)If count less than k, increase low

else high = midElse decrease high

return lowReturn k-th smallest distance

function smallestDistancePair(nums, k) {
    nums.sort((a, b) => a - b);
    const n = nums.length;
    function countPairs(mid) {
        let count = 0, left = 0;
        for (let right = 0; right < n; right++) {
            while (nums[right] - nums[left] > mid) {
                left++;
            }
            count += right - left;
        }
        return count;
    }

    let low = 0, high = nums[n - 1] - nums[0];
    while (low < high) {
        let mid = Math.floor((low + high) / 2);
        if (countPairs(mid) < k) {
            low = mid + 1;
        } else {
            high = mid;
        }
    }
    return low;
}

// Test
console.log(smallestDistancePair([1,3,1], 1)); // Output: 0

Line Notes

nums.sort((a, b) => a - b)Sort array for two-pointer counting

function countPairs(mid)Helper counts pairs with distance ≤ mid

while (nums[right] - nums[left] > mid)Move left pointer to maintain distance ≤ mid

count += right - leftAdd number of valid pairs ending at right

let low = 0, high = nums[n - 1] - nums[0]Initialize binary search range

if (countPairs(mid) < k)If fewer pairs than k, increase low

else high = midOtherwise, decrease high

return lowReturn k-th smallest distance

⏱

Complexity

TimeO(n log n + n log W), where W = max(nums) - min(nums)

SpaceO(1) or O(n) depending on sorting implementation

Sorting takes O(n log n). Binary searching the answer space takes O(log W). Each count uses two pointers in O(n).

💡 For n=10^5 and W=10^6, this approach is efficient enough for interviews and real use.

Interview Verdict: Accepted

This is the standard optimal approach for this problem and passes all tests efficiently.

🧠

Heap-based Approach (K-way Merge of Sorted Pairs)

💡 This approach uses a min-heap to generate pairs in ascending order of distance without enumerating all pairs, useful for understanding priority queues and lazy evaluation.

Intuition

Sort the array, then use a min-heap to push pairs starting with the smallest distances. Extract the smallest pair distance k times to find the k-th smallest.

Algorithm

1. Sort the array nums.
2. Initialize a min-heap and push pairs (nums[i], nums[i+1]) with their distances.
3. Pop the smallest distance pair from the heap k-1 times.
4. Each time you pop a pair (i, j), if j+1 < n, push the pair (i, j+1) into the heap.
5. After k-1 pops, the top of the heap is the k-th smallest pair distance.

💡 This simulates merging sorted lists of pair distances starting from each element, but can be slower due to heap operations.

</>

Code

import heapq

def smallestDistancePair(nums, k):
    nums.sort()
    n = len(nums)
    min_heap = []
    for i in range(n - 1):
        heapq.heappush(min_heap, (nums[i+1] - nums[i], i, i+1))

    for _ in range(k - 1):
        dist, i, j = heapq.heappop(min_heap)
        if j + 1 < n:
            heapq.heappush(min_heap, (nums[j+1] - nums[i], i, j + 1))
    return min_heap[0][0]

# Driver code
if __name__ == '__main__':
    print(smallestDistancePair([1,3,1], 1))  # Output: 0

Line Notes

nums.sort()Sort array to generate pairs in order

for i in range(n - 1)Initialize heap with pairs of adjacent elements

heapq.heappush(min_heap, (nums[i+1] - nums[i], i, i+1))Push initial pairs with their distances

dist, i, j = heapq.heappop(min_heap)Pop smallest distance pair

if j + 1 < nIf next pair exists for i, push it to heap

heapq.heappush(min_heap, (nums[j+1] - nums[i], i, j + 1))Push next pair from i to heap

return min_heap[0][0]Return k-th smallest pair distance

import java.util.*;
public class Solution {
    public int smallestDistancePair(int[] nums, int k) {
        Arrays.sort(nums);
        int n = nums.length;
        PriorityQueue<int[]> minHeap = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
        for (int i = 0; i < n - 1; i++) {
            minHeap.offer(new int[]{nums[i+1] - nums[i], i, i+1});
        }

        for (int count = 0; count < k - 1; count++) {
            int[] curr = minHeap.poll();
            int dist = curr[0], i = curr[1], j = curr[2];
            if (j + 1 < n) {
                minHeap.offer(new int[]{nums[j+1] - nums[i], i, j+1});
            }
        }
        return minHeap.peek()[0];
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.smallestDistancePair(new int[]{1,3,1}, 1)); // Output: 0
    }
}

Line Notes

Arrays.sort(nums)Sort array for ordered pair generation

PriorityQueue<int[]> minHeapMin-heap to store pairs by distance

minHeap.offer(new int[]{nums[i+1] - nums[i], i, i+1})Push initial adjacent pairs

int[] curr = minHeap.poll()Pop smallest distance pair

if (j + 1 < n)Check if next pair from i exists

minHeap.offer(new int[]{nums[j+1] - nums[i], i, j+1})Push next pair from i

return minHeap.peek()[0]Return k-th smallest pair distance

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

int smallestDistancePair(vector<int>& nums, int k) {
    sort(nums.begin(), nums.end());
    int n = nums.size();
    auto cmp = [](const tuple<int,int,int>& a, const tuple<int,int,int>& b) {
        return get<0>(a) > get<0>(b);
    };
    priority_queue<tuple<int,int,int>, vector<tuple<int,int,int>>, decltype(cmp)> minHeap(cmp);

    for (int i = 0; i < n - 1; i++) {
        minHeap.emplace(nums[i+1] - nums[i], i, i+1);
    }

    for (int count = 0; count < k - 1; count++) {
        auto [dist, i, j] = minHeap.top();
        minHeap.pop();
        if (j + 1 < n) {
            minHeap.emplace(nums[j+1] - nums[i], i, j+1);
        }
    }
    return get<0>(minHeap.top());
}

int main() {
    vector<int> nums = {1,3,1};
    cout << smallestDistancePair(nums, 1) << endl; // Output: 0
    return 0;
}

Line Notes

sort(nums.begin(), nums.end())Sort array for ordered pair generation

priority_queue<tuple<int,int,int>> minHeapMin-heap to store pairs by distance

minHeap.emplace(nums[i+1] - nums[i], i, i+1)Push initial adjacent pairs

auto [dist, i, j] = minHeap.top()Get smallest distance pair

minHeap.pop()Remove smallest pair from heap

if (j + 1 < n)Check if next pair from i exists

minHeap.emplace(nums[j+1] - nums[i], i, j+1)Push next pair from i

return get<0>(minHeap.top())Return k-th smallest pair distance

class MinHeap {
    constructor() {
        this.heap = [];
    }
    swap(i, j) {
        [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
    }
    push(val) {
        this.heap.push(val);
        this.bubbleUp();
    }
    bubbleUp() {
        let idx = this.heap.length - 1;
        while (idx > 0) {
            let parent = Math.floor((idx - 1) / 2);
            if (this.heap[parent][0] <= this.heap[idx][0]) break;
            this.swap(parent, idx);
            idx = parent;
        }
    }
    pop() {
        if (this.heap.length === 1) return this.heap.pop();
        const top = this.heap[0];
        this.heap[0] = this.heap.pop();
        this.bubbleDown();
        return top;
    }
    bubbleDown() {
        let idx = 0;
        const length = this.heap.length;
        while (true) {
            let left = 2 * idx + 1;
            let right = 2 * idx + 2;
            let smallest = idx;
            if (left < length && this.heap[left][0] < this.heap[smallest][0]) smallest = left;
            if (right < length && this.heap[right][0] < this.heap[smallest][0]) smallest = right;
            if (smallest === idx) break;
            this.swap(idx, smallest);
            idx = smallest;
        }
    }
    peek() {
        return this.heap[0];
    }
}

function smallestDistancePair(nums, k) {
    nums.sort((a, b) => a - b);
    const n = nums.length;
    const minHeap = new MinHeap();
    for (let i = 0; i < n - 1; i++) {
        minHeap.push([nums[i+1] - nums[i], i, i+1]);
    }

    for (let count = 0; count < k - 1; count++) {
        const [dist, i, j] = minHeap.pop();
        if (j + 1 < n) {
            minHeap.push([nums[j+1] - nums[i], i, j + 1]);
        }
    }
    return minHeap.peek()[0];
}

// Test
console.log(smallestDistancePair([1,3,1], 1)); // Output: 0

Line Notes

nums.sort((a, b) => a - b)Sort array for ordered pair generation

const minHeap = new MinHeap()Initialize min-heap for pairs

minHeap.push([nums[i+1] - nums[i], i, i+1])Push initial adjacent pairs

const [dist, i, j] = minHeap.pop()Pop smallest distance pair

if (j + 1 < n)Check if next pair from i exists

minHeap.push([nums[j+1] - nums[i], i, j + 1])Push next pair from i

return minHeap.peek()[0]Return k-th smallest pair distance

⏱

Complexity

TimeO(n log n + k log n)

SpaceO(n)

Sorting takes O(n log n). The heap can have up to n elements, and we perform k extractions and insertions each O(log n).

💡 For large k close to n^2, this approach is slower than binary search, but it is useful to understand heap usage.

Interview Verdict: Accepted but less efficient

This approach works but is less optimal for large inputs compared to binary search on answer space.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, the binary search + two-pointer approach is the best to code due to efficiency and clarity.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n^2 log n)	O(n^2)	No	N/A	Mention only - never code
2. Sorting + Binary Search + Two Pointers	O(n log n + n log W)	O(1) or O(n)	No	N/A	Code this approach
3. Heap-based K-way Merge	O(n log n + k log n)	O(n)	No	N/A	Mention as alternative, rarely code

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before your interview. Start by clarifying the problem, then explain the brute force approach to show understanding, and finally present the optimal binary search solution.

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Describe the brute force approach to demonstrate understanding.Step 3: Explain why brute force is inefficient and introduce sorting + binary search on answer space.Step 4: Detail the two-pointer counting method for pairs ≤ mid.Step 5: Code the binary search solution and test with examples.

Time Allocation

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

What the Interviewer Tests

The interviewer tests your ability to recognize binary search on answer space, implement two-pointer counting efficiently, and handle edge cases.

Common Follow-ups

• What if the array is very large and memory is limited? → Use streaming or external sorting.
• Can you find the k-th largest pair distance? → Modify binary search accordingly.

💡 These follow-ups test your adaptability and understanding of variations on the problem.

🔍

Pattern Recognition

When to Use

1) Asked for k-th smallest/largest element with constraints, 2) Pairwise distances or differences, 3) Large input size making brute force impossible, 4) Counting pairs ≤ some value is feasible.

Signature Phrases

'k-th smallest distance among pairs''count pairs with distance less than or equal to d'

NOT This Pattern When

Problems that ask for k-th element without pairwise constraints or without counting pairs do not fit this pattern.

Similar Problems

Find K-th Largest Element in an Array - similar selection problemFind Median of Two Sorted Arrays - binary search on answer spaceFind K-th Smallest Number in Multiplication Table - binary search counting

Practice

1. You are given a list of points on a 2D plane and need to find the k points closest to the origin (0,0). Which algorithmic approach best balances average time complexity and space usage for this problem?

easy

A. Use a Quickselect algorithm to partition points around a pivot distance until the k closest are identified.

B. Use a greedy algorithm that iteratively picks the closest point until k points are selected.

C. Use a dynamic programming approach to build up solutions for subsets of points.

D. Sort all points by their distance to the origin and return the first k points.

Solution

1. Step 1: Understand problem constraints

   The problem requires finding the k closest points efficiently, ideally better than sorting all points which is O(n log n).

2. Step 2: Identify algorithm characteristics

   Quickselect partitions points around a pivot and reduces the problem size each iteration, achieving average O(n) time and O(1) extra space, making it optimal.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Quickselect is known for average linear time selection problems [OK]

Hint: Quickselect offers average O(n) vs sorting's O(n log n) [OK]

Common Mistakes:

• Confusing sorting with selection algorithms
• Assuming greedy always works for closest points

2. What is the time complexity of the add(val) operation in the optimal min-heap approach for maintaining the kth largest element in a stream, assuming the heap size is k and the stream length is n?

medium

A. O(n ∙ log n) per add call, because the stream grows with n

B. O(1) per add call, as heap root access is constant time

C. O(k) per add call, because we may need to scan the heap to find the position

D. O(log k) per add call, since heap operations depend only on heap size k

Solution

1. Step 1: Identify heap size and operations

   The heap size is fixed at k, independent of stream length n. Each add involves either a push or a replace operation on the heap.

2. Step 2: Analyze complexity of heap operations

   Heap push or replace operations take O(log k) time because the heap has size k. Accessing the root is O(1), but add involves heapify steps.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Heap operations depend on k, not n, so O(log k) per add [OK]

Hint: Heap operations scale with heap size k, not stream length n [OK]

Common Mistakes:

• Confusing n with k in complexity
• Assuming linear scan of heap
• Ignoring heapify cost

3. What is the time complexity of the optimal sweep line algorithm for finding the maximum CPU load given n jobs, and why might a candidate incorrectly think it is higher?

medium

A. O(n^2) because each job is compared with every other job to find overlaps.

B. O(n log n) because of heap operations for each job's start and end.

C. O(n log n) due to sorting all start and end events, then a linear sweep.

D. O(n) because we only iterate through the jobs once.

Solution

1. Step 1: Identify the main cost is sorting 2n events.

   Sorting events takes O(n log n) time; sweeping through events is O(n).

2. Step 2: Explain why O(n^2) is incorrect.

   Brute force checking all pairs is O(n^2), but sweep line avoids pairwise comparisons by event sorting.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Sorting dominates, linear sweep after sorting [OK]

Hint: Sorting events dominates complexity [OK]

Common Mistakes:

• Confusing brute force O(n^2) with sweep line
• Ignoring sorting cost

4. The following code attempts to implement the optimal bucket sort approach for top k frequent elements. Identify the line that contains a subtle bug that can cause incorrect results or runtime errors.

medium

A. Line updating frequency dictionary with freq.get(num, 0) + 1

B. Line iterating over freq.items() to append elements to buckets

C. Line creating buckets with size max_freq instead of max_freq + 1

D. Line iterating buckets from max_freq - 1 down to 0

Solution

1. Step 1: Check bucket list size

   Buckets are created with size max_freq, but frequencies range from 1 to max_freq inclusive, so index max_freq is needed.

2. Step 2: Consequence of incorrect bucket size

   Accessing buckets[count] where count == max_freq causes IndexError or missing elements if bucket list is too small.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Bucket list must have max_freq + 1 slots to index frequencies correctly [OK]

Hint: Bucket size must be max_freq + 1 to include max frequency [OK]

Common Mistakes:

• Off-by-one bucket size
• Misindexing buckets causing runtime errors

5. Suppose the problem changes: you must find the k closest points to the origin, but points can be repeated multiple times (i.e., duplicates allowed and must be counted separately). Which modification to the Quickselect approach correctly handles this scenario without increasing time complexity significantly?

hard

A. Use a max heap of size k to keep track of closest points, allowing duplicates naturally.

B. Use a min heap to store all points and pop k times to get closest points, handling duplicates automatically.

C. Sort all points by distance and then remove duplicates before returning the first k points.

D. Modify Quickselect to partition points by distance and include duplicates in the partitioning logic without skipping any points.

Solution

1. Step 1: Understand duplicates impact

   Duplicates must be treated as distinct points; Quickselect partitions by distance and does not rely on uniqueness.

2. Step 2: Modify partition to handle duplicates correctly

   Partition logic remains the same; all points, including duplicates, are compared and placed correctly without skipping.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Quickselect handles duplicates naturally if partitioning is correct [OK]

Hint: Quickselect partitions all points regardless of duplicates [OK]

Common Mistakes:

• Using min heap instead of max heap
• Removing duplicates before selection
• Sorting all points unnecessarily