[LeetCode] Challenge log 378

Posted on |
378. Kth Smallest Element in a Sorted Matrix

Similar to #373: https://marcopolocai.github.io/2018/06/20/LeetCode-Challenge-log-373/.

However, because all we want is just the kth number, we can use a binary-search-like approach to make a guess and count if it has k-1 lower numbers. It is a faster approach but very tricky to implement, as you has to be very careful on the boundary.

Given a 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.

Example:

1
2
3
4
5
6
7
8
matrix = [
   [ 1,  5,  9],
   [10, 11, 13],
   [12, 13, 15]
],
k = 8,

return 13.

Note:
You may assume k is always valid, 1 ≤ k ≤ n2.

Soulution:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# piority queue approach
import heapq as hq
class Solution:
    def kthSmallest(self, matrix, k):
        """
        :type matrix: List[List[int]]
        :type k: int
        :rtype: int
        """
        if not matrix: return None
        n = len(matrix)
        count = 0
        visited = set()
        heap = [(matrix[0][0], 0, 0)]
        
        while count < k and len(heap)>0:
            num, i, j = hq.heappop(heap)
            if (i+1 < n) & ((i+1, j) not in visited): 
                hq.heappush(heap, (matrix[i+1][j], i+1, j))
                visited.add((i+1, j))
            if (j+1 < n) & ((i, j+1) not in visited):
                hq.heappush(heap, (matrix[i][j+1], i, j+1))
                visited.add((i, j+1))
            count += 1
        return num
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
# binary seach 
class Solution:
    def kthSmallest(self, matrix, k):
        """
        :type matrix: List[List[int]]
        :type k: int
        :rtype: int
        """
        def countLower(num, n, m):
            row = 0
            col = m - 1
            count = 0
            while row < n and col >= 0:
                if matrix[row][col] <= mid:
                    count += col + 1
                    row += 1
                else:
                    col -= 1
            return count
    
        n = len(matrix)
        low = matrix[0][0]
        high = matrix[-1][-1]
        
        while low < high:
            mid = (low + high) // 2
            count = countLower(mid, n, n)
            print(low, high, mid,count)
            if count >= k:
                high = mid 
            else:
                low = mid + 1
        return low
0%