🦄 Crystal Matrix: Kth Gleam

Difficulty: Intermediate Tags: heap, binary-search, matrix, merge-k-sorted Series: Algorithms I

Problem

Find the k-th smallest element in an n×n matrix where: - Each row is sorted from left to right - Each column is sorted from top to bottom

This is a special matrix with partial sorting - not fully sorted, but sorted in both dimensions!

Input

data = {
    'matrix': List[List[int]],  # n×n sorted matrix
    'k': int                     # Which smallest element to find (1-indexed)
}

Output

int  # The k-th smallest element

Constraints

• 1 ≤ n ≤ 1000 (matrix can be up to 1000×1000)
• 1 ≤ k ≤ n² (k is valid - won't ask for more elements than exist)
• Matrix values can be any integers

Examples

Example 1: Find 8th Smallest

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

Why?

Sorted order of all elements: [1, 5, 9, 10, 11, 12, 13, 13, 15]

Position:  1  2  3   4   5   6   7   8   9
Value:     1  5  9  10  11  12  13  13  15
                                   ↑
                               8th smallest

The 8th smallest element is 13.

Matrix visualization:

    Col0 Col1 Col2
Row0:  1    5    9
Row1: 10   11   13  ← This 13
Row2: 12   13   15  ← Also a 13

Example 2: Single Element

Input:  {'matrix': [[1]], 'k': 1}
Output: 1

Only one element, so the 1st smallest is 1.

Example 3: First Element

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

The 1st smallest is always the top-left corner (matrix[0][0]) because both rows and columns are sorted.

Example 4: Last Element

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

The last (4th) smallest element is the bottom-right corner.