Find The Kth Smallest Sum Of A Matrix With Sorted Rows - Leetcode Solution

Problem Statement:

You are given an m x n matrix mat, and an integer k, where k is less than or equal to the number of unique rows in the matrix. Return the kth smallest number in the matrix.

Input: mat = [[1,3,11],[2,4,6]], k = 5 Output: 7

Explanation: The 5th smallest number in the matrix is 7.

Solution:

The given matrix has sorted rows, but not necessarily sorted columns. We can use binary search to find the kth smallest number in the matrix.

We can define a search space based on the minimum and maximum values of the matrix. The minimum value will be the first element of the smallest row, and the maximum value will be the last element of the largest row.

We can start our search by taking the mid-point of the search space and counting the number of elements in the matrix that are less than or equal to the mid-point. If the count is less than k, we need to look for a larger mid-point; if the count is greater than or equal to k, we need to look for a smaller mid-point.

We can use binary search to iterate until we find the kth smallest number in the matrix.

Here is the step-by-step approach:

Step 1: Initialize the minimum and maximum values based on the first and last elements of the matrix.

l = mat[0][0]
r = mat[-1][-1]

Step 2: Use binary search to find the kth smallest number in the matrix.

while l < r:
    mid = (l + r) // 2
    count = 0
    j = len(mat[0]) - 1
    for i in range(len(mat)):
        while j >= 0 and mat[i][j] > mid:
            j -= 1
        count += (j + 1)
    if count < k:
        l = mid + 1
    else:
        r = mid

Step 3: Return the kth smallest number in the matrix.

return l

Time Complexity:

The binary search algorithm runs in O(log(max-min)). In each iteration of the while loop, we count the number of elements in the matrix that are less than or equal to the mid-point. This takes O(m) time, where m is the number of rows in the matrix. Therefore, the time complexity of the algorithm is O(m log(max-min)).

Space Complexity:

The space complexity of the algorithm is O(1), as we only store a constant number of variables in memory.

1