Kth Smallest Element in Sorted Matrix

📋

Problem

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.

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

Edge cases: k = 1 → returns smallest element in matrixk = n*n → returns largest element in matrixmatrix with duplicate elements → kth smallest counts duplicates

</>

IDE

def kthSmallest(matrix: list[list[int]], k: int) -> int:public int kthSmallest(int[][] matrix, int k)int kthSmallest(vector<vector<int>>& matrix, int k)function kthSmallest(matrix, k)

def kthSmallest(matrix, k):
    # Write your solution here
    pass

class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int kthSmallest(vector<vector<int>>& matrix, int k) {
    // Write your solution here
    return 0;
}

function kthSmallest(matrix, k) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: Wrong kth element due to off-by-one indexingUsing zero-based indexing incorrectly when k is 1-based✅ Adjust indexing by accessing k-1 element or popping heap k times

Wrong: Incorrect element due to greedy selection from rowsSelecting smallest elements from each row independently without global ordering✅ Use min-heap to merge rows or binary search counting instead of greedy

Wrong: Wrong count in binary search with negative numbersNot setting binary search low and high to matrix min and max values✅ Initialize low = matrix[0][0], high = matrix[n-1][n-1] and count elements <= mid correctly

Wrong: Wrong kth element when duplicates presentSkipping duplicates or miscounting elements in heap or binary search✅ Count duplicates properly and do not skip equal elements

Wrong: Timeout on large inputUsing brute force flatten and sort approach✅ Implement binary search on value range or min-heap merge approach

✓

Test Cases

Focus on handling smallest and largest k values and matrices with duplicates.

Watch out for common pitfalls like greedy selection and off-by-one errors.

Optimize your solution to avoid brute force and pass large input tests.

t1_01basic

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

Expected13

⏱ Performance - must finish in 2000ms

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

💡 Consider merging sorted rows or using a min-heap to track smallest elements.

💡 Use a min-heap to efficiently extract the smallest element k times.

💡 Push the first element of each row into a min-heap and pop k times, pushing next elements from the same row.

Why it failed: Incorrect output means heap or binary search logic is flawed; ensure you correctly track elements and their positions.

✓ Correctly finds kth smallest element using heap or binary search approach.

t1_02basic

Input{"matrix":[[-5,-4,-1],[0,3,5],[6,7,8]],"k":5}

Expected3

⏱ Performance - must finish in 2000ms

Sorted elements: [-5,-4,-1,0,3,5,6,7,8], 5th smallest is 5.

💡 Remember matrix rows and columns are sorted; use this property to optimize search.

💡 Binary search on value range can count how many elements are <= mid value.

💡 Adjust search range based on count until you find the exact kth smallest.

Why it failed: Wrong output indicates incorrect counting of elements <= mid or incorrect binary search boundaries.

✓ Correctly handles negative and positive values and finds kth smallest.

t2_01edge

Input{"matrix":[[42]],"k":1}

Expected42

⏱ Performance - must finish in 2000ms

Single element matrix; kth=1 smallest is the only element 42.

💡 Check behavior when matrix size is 1x1.

💡 Ensure no assumptions about multiple rows or columns.

💡 Return the single element directly when n=1.

Why it failed: Fails single element case due to indexing or loop assumptions; fix by handling n=1 correctly.

✓ Handles single element matrix correctly.

t2_02edge

Input{"matrix":[[1,2],[3,4]],"k":4}

Expected4

⏱ Performance - must finish in 2000ms

k equals n*n (4), so return largest element 4.

💡 Test boundary where k equals total elements.

💡 Ensure algorithm can return largest element correctly.

💡 Check binary search upper bound or heap extraction count.

Why it failed: Fails boundary k=n*n by returning smaller element; fix by correctly handling upper bound or heap extraction count.

✓ Correctly returns largest element when k equals total elements.

t2_03edge

Input{"matrix":[[2,2],[2,2]],"k":3}

Expected2

⏱ Performance - must finish in 2000ms

All elements identical; kth smallest is 2 regardless of k.

💡 Test matrix with all identical elements.

💡 Ensure duplicates are counted properly in kth selection.

💡 Avoid skipping duplicates in counting or heap logic.

Why it failed: Fails duplicate handling by skipping duplicates or miscounting; fix counting logic to include duplicates.

✓ Correctly counts duplicates and returns kth smallest.

t3_01corner

Input{"matrix":[[1,3,5],[6,7,12],[11,14,14]],"k":6}

Expected11

⏱ Performance - must finish in 2000ms

Sorted elements: [1,3,5,6,7,11,12,14,14], 6th smallest is 11.

💡 Beware of greedy approaches that pick smallest from each row without considering global order.

💡 Use min-heap or binary search to correctly merge sorted rows.

💡 Track element positions carefully to avoid skipping or double counting.

Why it failed: Greedy approach fails by picking local minimums only; fix by using min-heap or binary search counting.

✓ Correctly handles merging sorted rows without greedy mistakes.

t3_02corner

Input{"matrix":[[1,2,3],[4,5,6],[7,8,9]],"k":5}

Expected5

⏱ Performance - must finish in 2000ms

Sorted elements: [1,2,3,4,5,6,7,8,9], 5th smallest is 5.

💡 Check if algorithm confuses 0/1 indexing in k selection.

💡 Ensure k-th smallest means k-th element, not zero-based index.

💡 Adjust indexing when accessing sorted elements or heap pops.

Why it failed: Off-by-one error returns wrong element; fix by using k-1 indexing or correct heap pop count.

✓ Correctly handles 1-based k indexing.

t3_03corner

Input{"matrix":[[-10,-5,0],[1,2,3],[4,5,6]],"k":4}

Expected1

⏱ Performance - must finish in 2000ms

Sorted elements: [-10,-5,0,1,2,3,4,5,6], 4th smallest is 1.

💡 Check if algorithm handles negative numbers correctly in binary search.

💡 Ensure counting elements <= mid works with negative values.

💡 Adjust binary search range to include negative minimum.

Why it failed: Fails with negative numbers due to incorrect range or count; fix by setting low and high to matrix min and max.

✓ Correctly handles negative and positive values in binary search.

t4_01performance

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

Expectednull

⏱ Performance - must finish in 2000ms

n=300, O(n log(max-min)) binary search or O(k log n) heap approach must complete within 2 seconds.

💡 Brute force O(n^2 log n^2) will time out for n=300.

💡 Use binary search on value range or min-heap merge for efficiency.

💡 Avoid flattening entire matrix or naive sorting.

Why it failed: TLE due to brute force or inefficient approach; fix by implementing binary search or min-heap merge.

✓ Efficient algorithm runs within time limit.

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. Consider the following buggy Quickselect implementation. Which line contains the subtle bug that can cause incorrect results?

medium

A. Line 4: The comparison operator in the if condition inside partition

B. Line 7: The swap of nums[i] and nums[right]

C. Line 11: The base case check if left == right

D. Line 15: The recursive call when pivot_index < k

Solution

1. Step 1: Identify partition logic

   Partition should move elements greater than pivot to the left for kth largest.

2. Step 2: Locate bug

   The condition uses '<' instead of '>', reversing the order and breaking correctness.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Incorrect comparison flips partition logic [OK]

Hint: Partition comparison must match desired order (greater for kth largest) [OK]

Common Mistakes:

• Using wrong comparison direction in partition
• Confusing base case with recursion
• Swapping wrong elements

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

4. Suppose you want to find the kth largest element in an array where elements can be repeated and you want to find the kth largest unique element instead. Which modification to the Quickselect approach is correct?

hard

A. Use a min-heap of size k to store unique elements only, ignoring duplicates during insertion.

B. Run Quickselect as usual and then scan left and right to skip duplicates until kth unique is found.

C. Sort the array fully and iterate from largest to smallest counting unique elements until kth unique is reached.

D. Modify partition to skip duplicates and recurse only on unique elements.

Solution

1. Step 1: Understand uniqueness constraint

   Quickselect partitions by value but does not handle uniqueness inherently.

2. Step 2: Evaluate modifications

   Partial scanning or modifying partition is complex and error-prone; min-heap requires extra checks.

3. Step 3: Choose reliable approach

   Sorting fully and counting unique elements is straightforward and guarantees correctness.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Full sort enables unique counting easily [OK]

Hint: Uniqueness requires full sort or extra data structures [OK]

Common Mistakes:

• Assuming Quickselect handles uniqueness
• Trying to modify partition without correctness
• Ignoring duplicates in heap approach

5. Suppose you want to find the top k frequent words but now words can be reused infinitely many times (like unlimited supply). Which modification to the optimal bucket sort approach correctly handles this scenario?

hard

A. This problem reduces to a knapsack variant; bucket sort no longer applies

B. Modify frequency counting to consider infinite reuse, then apply bucket sort as usual

C. Use a dynamic programming approach to count combinations of words for frequencies

D. Use a max heap keyed by frequency and word lex order, repeatedly pop top k elements

Solution

1. Step 1: Understand infinite reuse impact

   Infinite reuse means frequency counts are not fixed; problem becomes combinatorial.

2. Step 2: Recognize problem class change

   Top k frequent words with unlimited reuse resembles knapsack or coin change, not simple frequency counting.

3. Step 3: Bucket sort no longer applies

   Bucket sort relies on fixed frequencies; dynamic programming or other combinatorial methods are needed.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Infinite reuse breaks frequency counting assumptions [OK]

Hint: Infinite reuse changes problem class, bucket sort invalid [OK]

Common Mistakes:

• Trying to reuse bucket sort with infinite counts
• Ignoring combinatorial explosion
• Assuming heap approach suffices