Kth Smallest Element in a Sorted Matrix

LeetCode 378

class Solution:
    def kthSmallest(self, matrix, k):
        """
        :type matrix: List[List[int]]
        :type k: int
        :rtype: int
        Note that it is the kth smallest element in the sorted order, 
        Not the kth Distinct element.
        """
        low = matrix[0][0]
        high = matrix [-1][-1]
        """
         [ [ 1,  5,  9],
           [10, 11, 13],
           [12, 13, 15]]
        k = 8 
        Result = 13
        
        1. mid = 8 : 在array中的位置 2 + 0 + 0 = 2
        2. low = 9 high = 15 mid = 12, 3 + 2 + 1 = 6
        3. low = 13 mid = 14 high = 15, 3 + 3 + 2 = 8
        4. low = 13 high 13 mid = 13, 3 + 3 + 2 = 8
        """
        while low <= high:
            mid = low + (high-low)//2
            # 
            res = 0
            for row in matrix:
                res += bisect.bisect(row, mid)                
            if res < k:
                low = mid + 1
            else:
                high = mid - 1
        return low