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. You are given a sorted array that has been rotated at an unknown pivot and may contain duplicates. You need to determine if a target value exists in this array efficiently. Which approach best guarantees an optimal average-case runtime while correctly handling duplicates?

easy

A. Use a simple linear scan through the array to find the target.

B. Apply a modified binary search that skips duplicates from both ends before deciding which half to search.

C. Use a classic binary search assuming no duplicates and no rotation.

D. Apply a dynamic programming approach to track possible target positions.

Solution

1. Step 1: Understand problem constraints

   The array is rotated and contains duplicates, which breaks classic binary search assumptions.

2. Step 2: Identify approach handling duplicates and rotation

   Modified binary search that skips duplicates at both ends before deciding the sorted half ensures correctness and efficiency.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Duplicates cause ambiguity; skipping them resolves it [OK]

Hint: Skip duplicates at boundaries before binary search [OK]

Common Mistakes:

• Assuming classic binary search works with duplicates
• Using DP unnecessarily
• Relying on linear scan for efficiency

2. Consider the following Python code implementing an integer square root using Newton's method. What is the value of guess after the first iteration of the while loop when x = 8?

easy

A. 3

B. 4

C. 2

D. 1

Solution

1. Step 1: Initialize variables for x=8

   Initial guess = 8 // 2 = 4.

2. Step 2: First iteration update

   Check 4*4=16 > 8, so update guess = (4 + 8 // 4) // 2 = (4 + 2) // 2 = 3.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   First guess update correctly computes to 3 [OK]

Hint: Initial guess halves x; update uses integer division [OK]

Common Mistakes:

• Off-by-one in guess update
• Confusing integer division with float
• Miscomputing initial guess

3. The following code attempts to find the k-th smallest number in an m x n multiplication table. Which line contains a subtle bug that can cause incorrect results for large inputs?

medium

A. Line 4: count = 0

B. Line 6: count += x // i # missing min with n

C. Line 8: if count >= k:

D. Line 13: mid = (low + high) // 2

Solution

1. Step 1: Identify counting logic

   The counting function must cap counts per row by n, since each row has only n elements.

2. Step 2: Analyze line 6

   Line 6 adds x // i without min(n, x // i), causing overcounting when x // i > n, leading to incorrect binary search decisions.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Bug causes wrong counts and incorrect final answer [OK]

Hint: Count per row capped by n to avoid overcounting [OK]

Common Mistakes:

• Forgetting min(n, x//i) in counting
• Incorrect mid calculation

4. What is the time complexity of the iterative fast exponentiation algorithm for computing x^n where n is a 32-bit integer?

medium

A. O(n)

B. O(n log n)

C. O(log n)

D. O(1)

Solution

1. Step 1: Identify loop iterations

   The algorithm halves n each iteration, so the loop runs approximately log₂(n) times.

2. Step 2: Confirm work per iteration

   Each iteration does a constant number of multiplications and divisions, so total time is O(log n).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Halving exponent each step -> logarithmic time [OK]

Hint: Halving exponent means O(log n) time [OK]

Common Mistakes:

• Confusing with O(n) from naive multiplication
• Assuming O(1) due to constant ops per iteration
• Thinking recursion adds extra complexity

5. Consider the following buggy code snippet for searching a target in a rotated sorted array with duplicates. Which line contains the subtle bug that can cause infinite loops or incorrect results?

medium

A. Line 9: if nums[mid] == target: return True

B. Line 7: mid = (left + right) // 2

C. Line 13: if nums[left] <= target < nums[mid]: right = mid - 1

D. Line 4: while left < right and nums[left] == nums[left + 1]: left += 1

Solution

1. Step 1: Identify duplicate skipping logic

   The code only skips duplicates from the left side, ignoring duplicates on the right side.

2. Step 2: Understand impact of skipping duplicates only on one side

   If duplicates exist on the right side, pointers may not move correctly, causing infinite loops or incorrect search decisions.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Skipping duplicates only on one side breaks correctness [OK]

Hint: Must skip duplicates from both ends to avoid infinite loops [OK]

Common Mistakes:

• Skipping duplicates only from left or right
• Not checking target at mid first
• Incorrect pointer updates