Given an n x n matrix where each of the rows and columns are 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.

Function Signature:

from typing import List

def kth_smallest(matrix: List[List[int]], k: int) -> int:
    """
    Find the kth smallest element in the sorted matrix.

    Parameters:
    - matrix: A square matrix (n x n) where each row and column is sorted.
    - k: The desired rank (1-indexed) of the smallest element.

    Returns:
    - int: The kth smallest element.
    """
    # Your code here

Example:

# Input: matrix = [
#    [ 1,  5,  9],
#    [10, 11, 13],
#    [12, 13, 15]
# ], k = 8
# Output: 13
# Explanation: The 8th smallest element in the matrix is 13.

# Input: matrix = [
#    [ 1,  3,  5],
#    [ 6,  7, 12],
#    [11, 14, 14]
# ], k = 2
# Output: 3
# Explanation: The 2nd smallest element in the matrix is 3.

# Input: matrix = [
#    [ 1,  5,  9],
#    [ 2,  6, 10],
#    [ 4,  7, 11]
# ], k = 3
# Output: 4
# Explanation: The 3rd smallest element in the matrix is 4.

Note:

  • You may assume that the matrix is non-empty and that 1 ≤ k ≤ n^2 where n is the size of the matrix.

Instructions:

  • Write the kth_smallest function to solve the problem.
  • Implement your solution in Python.
  • Provide clear comments in your code.
  • Discuss the time and space complexity of your solution.

As always, we’ll share our solution to this problem tomorrow. Stay tuned 😊