Kth Smallest Element in Sorted Matrix

🎯

Kth Smallest Element in Sorted Matrix

mediumHEAPAmazonGoogleFacebook

Imagine you have a large spreadsheet where each row is sorted, and you want to quickly find the kth smallest number without flattening the entire sheet.

💡 This problem is about efficiently selecting the kth smallest element from a 2D matrix where each row and column is sorted. Beginners often struggle because the matrix is sorted row-wise and column-wise, so naive flattening and sorting is inefficient. Understanding how to leverage the sorted rows and columns with heaps or binary search is key.

📋

Problem Statement

Given an n x n matrix where each of the rows and columns is sorted in ascending order, return the kth smallest element in the matrix. Note that it is the kth smallest element in the sorted order, not the kth distinct element. Input: matrix (List[List[int]]), integer k Output: integer representing the kth smallest element

n == matrix.length == matrix[i].length1 ≤ n ≤ 300-10^9 ≤ matrix[i][j] ≤ 10^91 ≤ k ≤ n^2

💡

Example

Input"matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8"

Output13

The sorted elements are [1,5,9,10,11,12,13,13,15], the 8th smallest is 13.

• k = 1 → returns smallest element in matrix
• k = n*n → returns largest element in matrix
• matrix with duplicate elements → kth smallest counts duplicates
• matrix with negative and positive numbers → handles full integer range

⚠️

Common Mistakes

Flattening matrix but forgetting to sort

Returns incorrect kth smallest element

✅ Always sort the flattened list before accessing kth element

Pushing all elements into heap instead of only first column elements

Heap grows too large, causing timeouts

✅ Only push first element of each row initially, then push next elements as you pop

Incorrectly counting elements ≤ mid in binary search

Binary search converges to wrong value

✅ Use two-pointer approach from bottom-left to count correctly

Off-by-one errors in indexing kth element

Returns wrong element (k-1 vs k confusion)

✅ Remember kth smallest is at index k-1 in zero-based arrays

Not handling duplicates properly

Incorrect kth element if duplicates exist

✅ Counting and heap approaches naturally handle duplicates; ensure code does not skip them

🧠

Brute Force (Flatten and Sort)

💡 This approach exists to build intuition by treating the matrix as a simple list and sorting it. It is straightforward but inefficient for large inputs, highlighting the need for better methods.

Intuition

Flatten the matrix into a single list, sort it, and pick the kth element. This uses no special properties of the matrix beyond sorting.

Algorithm

1. Create an empty list to hold all elements.
2. Iterate over each row and each element, appending to the list.
3. Sort the list in ascending order.
4. Return the element at index k-1.

💡 The main challenge is realizing that flattening ignores the matrix’s sorted structure, making it inefficient but conceptually simple.

</>

Code

def kthSmallest(matrix, k):
    flat = []
    for row in matrix:
        for num in row:
            flat.append(num)
    flat.sort()
    return flat[k-1]

# Driver code
if __name__ == '__main__':
    matrix = [[1,5,9],[10,11,13],[12,13,15]]
    k = 8
    print(kthSmallest(matrix, k))  # Output: 13

Line Notes

flat = []Initialize a list to hold all matrix elements

for row in matrix:Traverse each row to access all elements

flat.append(num)Add each element to the flat list

flat.sort()Sort all elements to find kth smallest easily

return flat[k-1]Return the kth smallest element (0-based index)

import java.util.*;
public class Solution {
    public static int kthSmallest(int[][] matrix, int k) {
        List<Integer> flat = new ArrayList<>();
        for (int[] row : matrix) {
            for (int num : row) {
                flat.add(num);
            }
        }
        Collections.sort(flat);
        return flat.get(k - 1);
    }

    public static void main(String[] args) {
        int[][] matrix = {{1,5,9},{10,11,13},{12,13,15}};
        int k = 8;
        System.out.println(kthSmallest(matrix, k)); // Output: 13
    }
}

Line Notes

List<Integer> flat = new ArrayList<>()Create list to hold all elements

for (int[] row : matrix)Iterate over each row

flat.add(num)Add each element to the list

Collections.sort(flat)Sort the list to find kth smallest

return flat.get(k - 1)Return kth smallest element by index

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

int kthSmallest(vector<vector<int>>& matrix, int k) {
    vector<int> flat;
    for (auto& row : matrix) {
        for (int num : row) {
            flat.push_back(num);
        }
    }
    sort(flat.begin(), flat.end());
    return flat[k - 1];
}

int main() {
    vector<vector<int>> matrix = {{1,5,9},{10,11,13},{12,13,15}};
    int k = 8;
    cout << kthSmallest(matrix, k) << endl; // Output: 13
    return 0;
}

Line Notes

vector<int> flat;Initialize vector to hold all elements

for (auto& row : matrix)Traverse each row

flat.push_back(num);Add each element to flat vector

sort(flat.begin(), flat.end());Sort all elements to find kth smallest

return flat[k - 1];Return kth smallest element by index

function kthSmallest(matrix, k) {
    const flat = [];
    for (const row of matrix) {
        for (const num of row) {
            flat.push(num);
        }
    }
    flat.sort((a, b) => a - b);
    return flat[k - 1];
}

// Test
const matrix = [[1,5,9],[10,11,13],[12,13,15]];
const k = 8;
console.log(kthSmallest(matrix, k)); // Output: 13

Line Notes

const flat = []Create array to hold all elements

for (const row of matrix)Iterate over each row

flat.push(num)Add each element to flat array

flat.sort((a, b) => a - b)Sort array numerically ascending

return flat[k - 1]Return kth smallest element by index

⏱

Complexity

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

SpaceO(n^2)

Flattening takes O(n^2), sorting takes O(n^2 log n^2), total dominated by sorting.

💡 For n=300, this means sorting 90,000 elements, which is expensive and slow for interviews.

Interview Verdict: TLE / Inefficient for large inputs

This approach is too slow for large matrices but is a good starting point to understand the problem.

🧠

Min Heap Merge (Merge k Sorted Lists)

💡 This approach leverages the sorted rows by merging them using a min heap, similar to merging k sorted lists. It is more efficient and uses the matrix’s sorted property.

Intuition

Use a min heap to keep track of the smallest unvisited elements from each row. Extract the smallest element k times to find the kth smallest.

Algorithm

1. Initialize a min heap and push the first element of each row along with its coordinates.
2. Pop the smallest element from the heap.
3. If there is a next element in the same row, push it into the heap.
4. Repeat steps 2-3 k times; the last popped element is the kth smallest.

💡 The heap always contains the next smallest candidates from each row, ensuring efficient selection.

</>

Code

import heapq

def kthSmallest(matrix, k):
    n = len(matrix)
    min_heap = []
    for r in range(min(k, n)):
        heapq.heappush(min_heap, (matrix[r][0], r, 0))
    count = 0
    while min_heap:
        val, r, c = heapq.heappop(min_heap)
        count += 1
        if count == k:
            return val
        if c + 1 < n:
            heapq.heappush(min_heap, (matrix[r][c+1], r, c+1))

# Driver code
if __name__ == '__main__':
    matrix = [[1,5,9],[10,11,13],[12,13,15]]
    k = 8
    print(kthSmallest(matrix, k))  # Output: 13

Line Notes

import heapqImport heapq for min heap operations

for r in range(min(k, n))Push first element of up to k rows to limit heap size

heapq.heappush(min_heap, (matrix[r][0], r, 0))Push tuple with value and coordinates

val, r, c = heapq.heappop(min_heap)Pop smallest element from heap

if c + 1 < n:If next element in row exists, push it to heap

import java.util.*;
public class Solution {
    public static int kthSmallest(int[][] matrix, int k) {
        int n = matrix.length;
        PriorityQueue<int[]> minHeap = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
        for (int r = 0; r < Math.min(k, n); r++) {
            minHeap.offer(new int[]{matrix[r][0], r, 0});
        }
        int count = 0;
        while (!minHeap.isEmpty()) {
            int[] curr = minHeap.poll();
            int val = curr[0], r = curr[1], c = curr[2];
            count++;
            if (count == k) return val;
            if (c + 1 < n) {
                minHeap.offer(new int[]{matrix[r][c + 1], r, c + 1});
            }
        }
        return -1; // Should never reach here
    }

    public static void main(String[] args) {
        int[][] matrix = {{1,5,9},{10,11,13},{12,13,15}};
        int k = 8;
        System.out.println(kthSmallest(matrix, k)); // Output: 13
    }
}

Line Notes

PriorityQueue<int[]> minHeap = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]))Min heap ordered by element value

for (int r = 0; r < Math.min(k, n); r++)Add first element of each row up to k rows

minHeap.offer(new int[]{matrix[r][0], r, 0})Store value and coordinates in heap

int[] curr = minHeap.poll()Extract smallest element from heap

if (c + 1 < n)Add next element in the same row if exists

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

int kthSmallest(vector<vector<int>>& matrix, int k) {
    int n = matrix.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 r = 0; r < min(k, n); r++) {
        minHeap.emplace(matrix[r][0], r, 0);
    }
    int count = 0;
    while (!minHeap.empty()) {
        auto [val, r, c] = minHeap.top();
        minHeap.pop();
        count++;
        if (count == k) return val;
        if (c + 1 < n) {
            minHeap.emplace(matrix[r][c + 1], r, c + 1);
        }
    }
    return -1; // Should not reach here
}

int main() {
    vector<vector<int>> matrix = {{1,5,9},{10,11,13},{12,13,15}};
    int k = 8;
    cout << kthSmallest(matrix, k) << endl; // Output: 13
    return 0;
}

Line Notes

auto cmp = [](const tuple<int,int,int>& a, const tuple<int,int,int>& b)Comparator for min heap by value

priority_queue<tuple<int,int,int>, vector<tuple<int,int,int>>, decltype(cmp)> minHeap(cmp)Declare min heap with custom comparator

minHeap.emplace(matrix[r][0], r, 0)Push first element of each row with coordinates

auto [val, r, c] = minHeap.top()Extract smallest element tuple

if (c + 1 < n)Push next element in the same row if exists

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 === 0) return undefined;
        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;
        }
    }
    size() {
        return this.heap.length;
    }
}

function kthSmallest(matrix, k) {
    const n = matrix.length;
    const minHeap = new MinHeap();
    for (let r = 0; r < Math.min(k, n); r++) {
        minHeap.push([matrix[r][0], r, 0]);
    }
    let count = 0;
    while (minHeap.size() > 0) {
        const [val, r, c] = minHeap.pop();
        count++;
        if (count === k) return val;
        if (c + 1 < n) {
            minHeap.push([matrix[r][c + 1], r, c + 1]);
        }
    }
    return -1; // Fallback, should not reach here
}

// Test
const matrix = [[1,5,9],[10,11,13],[12,13,15]];
const k = 8;
console.log(kthSmallest(matrix, k)); // Output: 13

Line Notes

class MinHeapCustom min heap implementation to manage elements

minHeap.push([matrix[r][0], r, 0])Push first element of each row with coordinates

const [val, r, c] = minHeap.pop()Pop smallest element from heap

if (count === k) return valReturn kth smallest when count matches

if (c + 1 < n)Push next element in the same row if exists

⏱

Complexity

TimeO(k log n)

SpaceO(n)

Heap size is at most n, each of k pops and pushes costs log n, total O(k log n).

💡 For n=300 and k=1000, this is much faster than sorting all elements.

Interview Verdict: Accepted and efficient for medium-sized inputs

This approach balances simplicity and efficiency, making it a strong candidate in interviews.

🧠

Binary Search on Value Range

💡 This approach uses binary search on the range of possible values rather than indices, leveraging the matrix’s sorted property to count how many elements are ≤ mid.

Intuition

Since the matrix is sorted row-wise and column-wise, we can guess a value mid and count how many elements are ≤ mid. Adjust search range based on count until we find the kth smallest.

Algorithm

1. Set low to matrix[0][0] and high to matrix[n-1][n-1].
2. While low < high, compute mid = (low + high) // 2.
3. Count how many elements in the matrix are ≤ mid using a row-wise pointer.
4. If count < k, set low = mid + 1; else set high = mid.
5. Return low as the kth smallest element.

💡 Counting elements ≤ mid efficiently is key; we use the sorted rows to do this in O(n) per count.

</>

Code

def kthSmallest(matrix, k):
    n = len(matrix)
    low, high = matrix[0][0], matrix[-1][-1]

    def countLessEqual(mid):
        count = 0
        row, col = n - 1, 0
        while row >= 0 and col < n:
            if matrix[row][col] <= mid:
                count += row + 1
                col += 1
            else:
                row -= 1
        return count

    while low < high:
        mid = (low + high) // 2
        if countLessEqual(mid) < k:
            low = mid + 1
        else:
            high = mid
    return low

# Driver code
if __name__ == '__main__':
    matrix = [[1,5,9],[10,11,13],[12,13,15]]
    k = 8
    print(kthSmallest(matrix, k))  # Output: 13

Line Notes

low, high = matrix[0][0], matrix[-1][-1]Initialize search range from smallest to largest element

def countLessEqual(mid)Helper to count elements ≤ mid efficiently

while row >= 0 and col < nTraverse matrix from bottom-left to top-right

if matrix[row][col] <= midIf element ≤ mid, all above in column are ≤ mid

if countLessEqual(mid) < kAdjust search range based on count

public class Solution {
    public static int kthSmallest(int[][] matrix, int k) {
        int n = matrix.length;
        int low = matrix[0][0], high = matrix[n - 1][n - 1];

        while (low < high) {
            int mid = low + (high - low) / 2;
            int count = countLessEqual(matrix, mid);
            if (count < k) low = mid + 1;
            else high = mid;
        }
        return low;
    }

    private static int countLessEqual(int[][] matrix, int mid) {
        int count = 0, n = matrix.length;
        int row = n - 1, col = 0;
        while (row >= 0 && col < n) {
            if (matrix[row][col] <= mid) {
                count += row + 1;
                col++;
            } else {
                row--;
            }
        }
        return count;
    }

    public static void main(String[] args) {
        int[][] matrix = {{1,5,9},{10,11,13},{12,13,15}};
        int k = 8;
        System.out.println(kthSmallest(matrix, k)); // Output: 13
    }
}

Line Notes

int low = matrix[0][0], high = matrix[n - 1][n - 1]Initialize binary search range

while (low < high)Binary search loop to narrow down kth smallest

int count = countLessEqual(matrix, mid)Count elements ≤ mid

if (matrix[row][col] <= mid)If element ≤ mid, add all elements above in column

if (count < k) low = mid + 1Adjust low or high based on count

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

int countLessEqual(const vector<vector<int>>& matrix, int mid) {
    int n = matrix.size();
    int count = 0, row = n - 1, col = 0;
    while (row >= 0 && col < n) {
        if (matrix[row][col] <= mid) {
            count += row + 1;
            col++;
        } else {
            row--;
        }
    }
    return count;
}

int kthSmallest(vector<vector<int>>& matrix, int k) {
    int n = matrix.size();
    int low = matrix[0][0], high = matrix[n - 1][n - 1];
    while (low < high) {
        int mid = low + (high - low) / 2;
        if (countLessEqual(matrix, mid) < k) {
            low = mid + 1;
        } else {
            high = mid;
        }
    }
    return low;
}

int main() {
    vector<vector<int>> matrix = {{1,5,9},{10,11,13},{12,13,15}};
    int k = 8;
    cout << kthSmallest(matrix, k) << endl; // Output: 13
    return 0;
}

Line Notes

int low = matrix[0][0], high = matrix[n - 1][n - 1]Set initial binary search bounds

while (low < high)Binary search loop to find kth smallest

if (matrix[row][col] <= mid)Count all elements in column ≤ mid

count += row + 1Add all elements above current row in column

if (countLessEqual(matrix, mid) < k)Adjust search range based on count

function countLessEqual(matrix, mid) {
    const n = matrix.length;
    let count = 0, row = n - 1, col = 0;
    while (row >= 0 && col < n) {
        if (matrix[row][col] <= mid) {
            count += row + 1;
            col++;
        } else {
            row--;
        }
    }
    return count;
}

function kthSmallest(matrix, k) {
    const n = matrix.length;
    let low = matrix[0][0], high = matrix[n - 1][n - 1];
    while (low < high) {
        const mid = Math.floor((low + high) / 2);
        if (countLessEqual(matrix, mid) < k) {
            low = mid + 1;
        } else {
            high = mid;
        }
    }
    return low;
}

// Test
const matrix = [[1,5,9],[10,11,13],[12,13,15]];
const k = 8;
console.log(kthSmallest(matrix, k)); // Output: 13

Line Notes

let low = matrix[0][0], high = matrix[n - 1][n - 1]Initialize binary search bounds

while (row >= 0 && col < n)Traverse matrix from bottom-left to top-right

if (matrix[row][col] <= mid)Count all elements in column ≤ mid

count += row + 1Add all elements above current row in column

if (countLessEqual(matrix, mid) < k)Adjust search range based on count

⏱

Complexity

TimeO(n log(max - min))

SpaceO(1)

Binary search over value range takes log(max-min) steps; each count is O(n).

💡 For n=300 and value range ~10^9, this is very efficient compared to flattening.

Interview Verdict: Accepted and optimal for large inputs

This approach is the most scalable and elegant, ideal for interviews if you understand it.

📊

All Approaches - One-Glance Tradeoffs

💡 In most interviews, approach 2 (min heap) or 3 (binary search) are preferred. Brute force is only for initial explanation.

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. Min Heap Merge	O(k log n)	O(n)	No	Yes	Good to code if comfortable with heaps
3. Binary Search on Value Range	O(n log(max-min))	O(1)	No	Yes	Optimal approach, best if you understand binary search on answer

💼

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 the problem and constraints with the interviewer.Step 2: Describe the brute force approach to show understanding.Step 3: Introduce the min heap merge approach leveraging sorted rows.Step 4: Present the binary search on value range as the optimal solution.Step 5: Code the chosen approach carefully and test edge cases.

Time Allocation

Clarify: 3min → Approach discussion: 7min → Code: 10min → Testing & optimization: 5min. Total ~25min

What the Interviewer Tests

Interviewer tests your ability to leverage sorted data structures, optimize time complexity, and write clean, bug-free code.

Common Follow-ups

• What if the matrix is not square? → The heap and binary search approaches still work with minor adjustments.
• Can you find kth largest instead? → Reverse the logic or adjust binary search accordingly.

💡 These follow-ups test your flexibility and understanding of the core techniques beyond the base problem.

🔍

Pattern Recognition

When to Use

1) Matrix or multiple sorted lists, 2) Need kth smallest/largest, 3) Rows or columns sorted, 4) Constraints too large for naive sorting

Signature Phrases

'kth smallest element in sorted matrix''each row and column is sorted'

NOT This Pattern When

Problems where matrix is unsorted or only partially sorted, or where k-selection is on unsorted arrays without constraints

Similar Problems

Merge k Sorted Lists - uses min heap to merge sorted sequencesFind Median in a Row-wise Sorted Matrix - uses binary search on value rangeKth Largest Element in an Array - simpler k-selection problem

Practice

1. You are given an unsorted array and need to find the element that ranks kth when the array is sorted in descending order. Which algorithmic approach is best suited to find this element efficiently without fully sorting the array?

easy

A. Sort the entire array and pick the kth element from the end.

B. Use a greedy algorithm that picks the largest elements one by one until kth is reached.

C. Use a dynamic programming approach to build solutions for smaller subproblems.

D. Use a partition-based selection algorithm that partially sorts the array around a pivot.

Solution

1. Step 1: Understand problem requirements

   The problem asks for the kth largest element without fully sorting the array, so a full sort is not optimal.

2. Step 2: Identify suitable algorithm

   Partition-based selection (Quickselect) partially sorts the array around pivots, achieving average O(n) time, which is more efficient than sorting.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Partial sorting via partitioning -> efficient selection [OK]

Hint: Partial sorting via partitioning is faster than full sorting [OK]

Common Mistakes:

• Assuming full sort is always needed
• Confusing greedy with selection
• Thinking DP applies here

2. You are given a 2D matrix and need to find the kth largest value among all XOR coordinate values, where each coordinate value is the XOR of all elements from the top-left corner to that coordinate. Which approach guarantees an optimal solution in terms of time complexity?

easy

A. Use nested loops to compute XOR for each coordinate independently, then sort all values.

B. Apply dynamic programming with memoization to store XOR values and then sort them.

C. Use a greedy approach to pick the largest elements first and XOR them until k values are found.

D. Compute a prefix XOR matrix and maintain a min-heap of size k to track the kth largest value.

Solution

1. Step 1: Understand the problem constraints

   Computing XOR values for each coordinate independently with nested loops leads to O(m^2 * n^2) time, which is inefficient.

2. Step 2: Recognize prefix XOR and min-heap usage

   Using a prefix XOR matrix allows O(m * n) computation of all XOR coordinate values. Maintaining a min-heap of size k ensures we track the kth largest value efficiently, leading to O(m * n * log k) time.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Prefix XOR + min-heap is optimal for kth largest XOR coordinate value [OK]

Hint: Prefix XOR + min-heap is optimal for kth largest XOR values [OK]

Common Mistakes:

• Thinking nested loops with sorting is efficient enough
• Assuming greedy selection works for XOR
• Confusing DP with prefix XOR usage

3. Examine the following buggy Quickselect code for finding k closest points. Which line contains the subtle bug that can cause incorrect results or failure on edge cases?

def kClosest(points: List[List[int]], k: int) -> List[List[int]]:
    def dist(i):
        return (points[i][0]**2 + points[i][1]**2)**0.5  # Bug here

    def partition(left, right, pivot_index):
        pivot_dist = dist(pivot_index)
        points[pivot_index], points[right] = points[right], points[pivot_index]
        store_index = left
        for i in range(left, right):
            if dist(i) < pivot_dist:
                points[store_index], points[i] = points[i], points[store_index]
                store_index += 1
        points[right], points[store_index] = points[store_index], points[right]
        return store_index

    def quickselect(left, right, k_smallest):
        if left == right:
            return
        pivot_index = random.randint(left, right)
        pivot_index = partition(left, right, pivot_index)
        if k_smallest == pivot_index:
            return
        elif k_smallest < pivot_index:
            quickselect(left, pivot_index - 1, k_smallest)
        else:
            quickselect(pivot_index + 1, right, k_smallest)

    quickselect(0, len(points) - 1, k - 1)
    return points[:k]

medium

A. Line defining dist(i) using sqrt in distance calculation

B. Line swapping pivot with right element in partition

C. Line incrementing store_index inside partition loop

D. Line returning points[:k] after quickselect completes

Solution

1. Step 1: Identify inefficiency in distance calculation

   Using sqrt is unnecessary since squared distances preserve order and avoids floating-point overhead.

2. Step 2: Understand impact on correctness and performance

   Using sqrt slows down comparisons and can introduce floating-point precision issues, potentially causing incorrect partitioning.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Removing sqrt improves speed and correctness [OK]

Hint: Avoid sqrt; squared distances suffice for comparison [OK]

Common Mistakes:

• Using sqrt unnecessarily
• Misplacing pivot swaps
• Incorrect slicing after quickselect

4. What is the average and worst-case time complexity of the Quickselect algorithm for finding the kth largest element in an unsorted array of size n?

medium

A. Average O(n log n), Worst O(n^2)

B. Average O(n), Worst O(n^2)

C. Average O(n^2), Worst O(n^2)

D. Average O(n), Worst O(n log n)

Solution

1. Step 1: Analyze average case

   Quickselect partitions array and recurses on one side, averaging O(n) time.

2. Step 2: Analyze worst case

   Poor pivot choices cause unbalanced partitions, degrading to O(n^2) time.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Average linear, worst quadratic time complexity [OK]

Hint: Average linear time, worst quadratic due to bad pivots [OK]

Common Mistakes:

• Assuming always O(n log n)
• Confusing average and worst cases
• Ignoring worst-case pivot effects

5. What is the time complexity of the optimal bucket sort approach for finding the top k frequent words from a list of n words, assuming the maximum frequency is m and average word length is constant?

medium

A. O(n log n) due to sorting all unique words

B. O(n m) because sorting words within buckets depends on max frequency m

C. O(n) because frequency counting and bucket placement are linear, and sorting within buckets is bounded

D. O(k log n) because extracting top k from a heap dominates

Solution

1. Step 1: Analyze frequency counting

   Counting frequencies is O(n) since each word is processed once.

2. Step 2: Analyze bucket placement and sorting

   Words are placed into buckets indexed by frequency; sorting within each bucket is lexicographic but total words sum to n, so total sorting cost is O(n).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Overall time is linear in n with lex sort bounded by total words [OK]

Hint: Bucket sort + lex sort within buckets is O(n) total [OK]

Common Mistakes:

• Assuming full sort is needed (O(n log n))
• Confusing max frequency m as multiplicative factor
• Thinking heap extraction dominates