Kth Smallest Element in a Sorted Matrix

Data Structures and Algorithms

Statement

Find the kth smallest value of a ( n × n ) matrix, where each row and column is sorted in ascending order. There can be repeated values in the matrix, but each value is considered unique, and so contributes to finding the kth smallest value.

Constraints

• matrix.length() = n
• matrix[i].length() = n
• 1 ≤ n ≤ 100
• -10³ ≤ matrix[i][j] ≤ 10³
• 1 ≤ k ≤ n^2

Solution

"""
production algorithm
"""

from algorithms.k_way_merge.kth_smallest_number.solution import Solution as Solution2


class Solution:
    def kth_smallest_number(self, matrix, k):
        """
        time complexity O(klogn)
        space complexity O(n)
        """
        solution2 = Solution2()
        return solution2.k_smallest_number(matrix, k)

"""
unit tests
"""

from unittest import TestCase
from algorithms.k_way_merge.kth_smallest_number_of_sorted_matrix.solution import Solution


class SolutionTestCase(TestCase):
    def test_empty_matrix(self):
        # Given
        matrix = []
        k = 7
        solution = Solution()

        # When
        actual = solution.kth_smallest_number(matrix, k)

        # Then
        expected = 0
        self.assertEqual(actual, expected)

    def test_matrix_smaller_than_k(self):
        # Given
        matrix = [[24, 26],
                  [34, 36]]
        k = 7
        solution = Solution()

        # When
        actual = solution.kth_smallest_number(matrix, k)

        # Then
        expected = 36
        self.assertEqual(actual, expected)

    def test_matrix_larger_than_k(self):
        # Given
        matrix = [[51, 53, 55, 57, 59],
                  [61, 63, 65, 67, 69],
                  [71, 73, 75, 77, 79],
                  [81, 83, 85, 87, 89],
                  [91, 93, 95, 97, 99]]
        k = 7
        solution = Solution()

        # When
        actual = solution.kth_smallest_number(matrix, k)

        # Then
        expected = 63
        self.assertEqual(actual, expected)

Strategy

K-way Merge.

Explanation

Find the kth smallest number of a sorted matrix, is a specialization of find the kth smallest number of m sorted lists [link]. In the latter problem, lists can be variable length or empty. In the former problem, rows of the matrix are all equal length n.

Time Complexity

The time complexity of the algorithm is O(klogn).

Space Complexity

The auxiliary space complexity of the algorithm is O(n).

Links

data_structures_algorithms/algorithms/k_way_merge/kth_smallest_number_of_sorted_matrix at main ·…