Kth Smallest in Sorted Matrix

📋

Problem

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

Given an n x n matrix where each of the rows and columns is sorted in ascending order, find 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]]), k (int) Output: int (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 → smallest element in the matrixk = n*n → largest element in the matrixmatrix with all identical elements → kth smallest is that element

</>

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 smallest value due to counting elements < mid instead of <= midCount function excludes elements equal to mid, causing off-by-one errors.✅ Change count condition from 'element < mid' to 'element <= mid' in counting function.

Wrong: Output is the smallest or largest element regardless of kBinary search boundaries not updated correctly or count function always returns incorrect counts.✅ Ensure binary search low and high boundaries are initialized to matrix[0][0] and matrix[n-1][n-1], and count function returns accurate counts.

Wrong: Output is incorrect due to greedy approach picking elements row-wiseAlgorithm picks elements greedily without counting all elements <= mid properly.✅ Implement count function scanning from bottom-left or top-right to count elements <= mid correctly.

Wrong: Timeout or no output on large inputsUsing brute force approach sorting all elements instead of binary search on value range.✅ Implement binary search on value range with O(n) counting to reduce complexity from O(n^2 log n) to O(n log(max-min)).

✓

Test Cases

Focus on handling smallest and largest k values and single-element matrices correctly.

Avoid greedy selection; implement precise counting of elements <= mid.

Optimize your solution to binary search on value range with O(n) counting to pass large inputs.

t1_01basic

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

Expected13

⏱ Performance - must finish in 2000ms

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

💡 Consider binary searching the value range between the smallest and largest elements.

💡 Use a helper function to count how many elements are less than or equal to mid.

💡 Adjust search boundaries based on count to find the kth smallest value.

Why it failed: Incorrect output means counting or binary search boundaries are wrong; ensure count of elements <= mid is computed correctly and binary search updates low/high properly.

✓ Correctly finds kth smallest using binary search on value range.

t1_02basic

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

Expected5

⏱ Performance - must finish in 2000ms

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

💡 Binary search on the value range from 1 to 9.

💡 Count elements <= mid to decide search direction.

💡 When count >= k, move high down; else move low up.

Why it failed: If output is wrong, likely count function or binary search update logic is incorrect; verify counting elements <= mid and boundary updates.

✓ Binary search and counting logic correctly identify kth smallest.

t2_01edge

Input{"matrix":[[-5]],"k":1}

Expected-5

⏱ Performance - must finish in 2000ms

Single element matrix; kth=1 smallest is that element itself.

💡 Check behavior with smallest possible matrix size.

💡 Ensure code handles single-element matrices without errors.

💡 Return the only element when k=1 and n=1.

Why it failed: Fails single element test if code assumes larger matrix; fix by handling n=1 case correctly.

✓ Handles single element matrix correctly.

t2_02edge

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

Expected2

⏱ Performance - must finish in 2000ms

All elements identical; kth smallest is the identical element 2.

💡 Test with all identical elements to check counting logic.

💡 Counting elements <= mid should count all elements if mid >= element value.

💡 Binary search should converge to the identical element value.

Why it failed: Fails identical elements test if count function or binary search does not handle duplicates properly; fix count to include all equal elements.

✓ Correctly handles all identical elements.

t2_03edge

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

Expected-10

⏱ Performance - must finish in 2000ms

k=1 means smallest element, which is -10 here.

💡 Check that code correctly identifies smallest element for k=1.

💡 Binary search low boundary should start at matrix[0][0].

💡 Count function must count elements <= mid correctly for negative values.

Why it failed: Fails smallest element test if low boundary or count function mishandles negative values; fix by initializing low to matrix[0][0] and counting properly.

✓ Correctly returns smallest element for k=1.

t3_01corner

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

Expected11

⏱ Performance - must finish in 2000ms

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

💡 Beware of greedy approaches that pick elements row-wise without counting properly.

💡 Use binary search on value range with count of elements <= mid.

💡 Fix: implement count function scanning from bottom-left or top-right to count efficiently.

Why it failed: Fails greedy trap test if code picks elements incorrectly without counting all <= mid; fix by implementing correct count function scanning matrix.

✓ Correctly counts elements and finds kth smallest avoiding greedy trap.

t3_02corner

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

Expected9

⏱ Performance - must finish in 2000ms

k=n*n=9 means largest element, which is 9.

💡 Check boundary condition when k equals total elements.

💡 Binary search high boundary should be matrix[n-1][n-1].

💡 Ensure count function and binary search handle upper boundary correctly.

Why it failed: Fails exact boundary test if high boundary or count function mishandles max element; fix by initializing high to matrix[n-1][n-1] and counting correctly.

✓ Correctly returns largest element for k=n*n.

t3_03corner

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

Expected2

⏱ Performance - must finish in 2000ms

Sorted order: [1,2,2,3,3,3,4,4,5], 4th smallest is 2.

💡 Beware off-by-one errors in counting elements <= mid.

💡 Count function must include elements equal to mid, not just less than.

💡 Fix: use <= mid in count comparisons, not < mid.

Why it failed: Fails off-by-one test if count excludes elements equal to mid; fix by counting elements <= mid, not < mid.

✓ Correctly counts elements including equals and finds kth smallest.

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 solution must complete within 2 seconds.

💡 Brute force O(n^2 log n^2) will time out here.

💡 Use binary search on value range with O(n) count per iteration.

💡 Optimize count function to run in O(n) by scanning from bottom-left.

Why it failed: TLE due to brute force or inefficient counting; fix by implementing binary search on value range with O(n) counting.

✓ Efficient binary search with O(n log(max-min)) complexity confirmed.

Practice

1. Given the following code implementing the optimal search in a rotated array with duplicates, what is the return value when calling search([1,1,3,1], 3)?

easy

A. True

B. False

C. Index of target (2)

D. Raises an error due to duplicates

Solution

1. Step 1: Initial pointers and duplicates skipping

   Input: [1,1,3,1], target=3; left=0, right=3. Skip duplicates at left: nums[0]==nums[1], left increments to 1. Skip duplicates at right: nums[3]==nums[2], right decrements to 2.

2. Step 2: Calculate mid and compare

   mid = (1+2)//2=1; nums[1]=1 != target. Left half sorted since nums[left]=1 <= nums[mid]=1. Target 3 not in [1,1), so left=mid+1=2. Now left=2, right=2; mid=2; nums[2]=3 == target -> return True.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Duplicates skipped correctly; target found at mid [OK]

Hint: Duplicates skipped before mid calculation [OK]

Common Mistakes:

• Not skipping duplicates causing infinite loop
• Miscomputing mid index
• Returning index instead of boolean

2. What is the time complexity of the optimal approach that performs binary search on each row of an m x n matrix to find a target value?

medium

A. O(log m * log n)

B. O(m * n)

C. O(m * log n)

D. O(m + n)

Solution

1. Step 1: Identify outer loop complexity

   We iterate over m rows, so outer loop is O(m).

2. Step 2: Identify inner binary search complexity

   Binary search on each row of length n takes O(log n).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Overall complexity is O(m * log n), not O(m*n) or O(log m * log n) [OK]

Hint: Binary search is logarithmic per row [OK]

Common Mistakes:

• Confusing with brute force O(m*n)
• Thinking binary search applies to columns too
• Assuming double log complexity

3. What is the time complexity of the optimal solution that uses binary search on the answer space combined with prefix sums and binary search for feasibility checks in the Split Array Largest Sum problem?

medium

A. O(n log(sum(nums))) since binary search is done only on sums without extra binary searches

B. O(n^m) due to exploring all splits recursively

C. O(n^2 log(sum(nums))) because feasibility check scans all subarrays linearly

D. O(n log n log(sum(nums))) because each binary search iteration uses binary search on prefix sums

Solution

1. Step 1: Identify outer binary search on answer space

   Binary search on possible sums takes O(log(sum(nums))) iterations.

2. Step 2: Analyze feasibility check using binary search on prefix sums

   Each feasibility check uses binary search (O(log n)) for each subarray, repeated up to n times -> O(n log n).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Nested binary searches yield O(n log n log(sum(nums))) [OK]

Hint: Feasibility check uses binary search inside binary search [OK]

Common Mistakes:

• Assuming feasibility check is O(n) ignoring binary search
• Confusing n and m in complexity
• Ignoring log factor from binary search on sums

4. Suppose the problem is modified so that the multiplication table allows repeated use of the same row and column indices (i.e., infinite repetitions of each product). Which of the following changes to the algorithm is correct to find the k-th smallest number under this new condition?

hard

A. Use the same binary search with the counting function unchanged, since repetition doesn't affect counts.

B. Switch to generating all products up to k and sorting them, since binary search no longer applies.

C. Use a min-heap to generate products in ascending order with duplicates allowed, extracting k elements.

D. Modify the counting function to remove the cap by n, counting all multiples less than or equal to x for each i.

Solution

1. Step 1: Understand the new problem condition

   Allowing infinite repetitions means the multiplication table is conceptually infinite, so counting by rows capped at n no longer applies.

2. Step 2: Analyze algorithmic implications

   Binary search with counting function fails because counts become infinite or undefined; generating all values is impossible.

3. Step 3: Use a min-heap approach

   A min-heap can generate products in ascending order with duplicates allowed, extracting the k-th smallest efficiently.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Min-heap approach handles infinite repetitions correctly [OK]

Hint: Infinite repetitions break counting; use min-heap [OK]

Common Mistakes:

• Assuming counting function unchanged
• Trying to generate all values

5. Suppose the array can contain duplicate elements and you want to find the first position where the target can be inserted (i.e., the leftmost insertion point). Which modification to the binary search algorithm correctly achieves this?

hard

A. When nums[mid] >= target, recurse on the left half; else recurse on the right half.

B. Change the base case to return right instead of left when left > right.

C. When nums[mid] > target, recurse on the right half; else recurse on the left half.

D. Use linear scan after binary search to find the first occurrence.

Solution

1. Step 1: Understand requirement for leftmost insertion

   We must find the earliest index where target can be inserted, including duplicates.

2. Step 2: Modify binary search condition

   If nums[mid] >= target, recurse left to find earlier occurrence; else recurse right.

3. Step 3: Avoid linear scan for efficiency

   Linear scan after binary search defeats O(log n) goal.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Condition ensures leftmost insertion index found efficiently [OK]

Hint: For leftmost insert, recurse left on >= target [OK]

Common Mistakes:

• Recursing right on >= target misses leftmost index
• Returning right instead of left at base case
• Using linear scan after binary search