Python 3-line Solution


  • 0

    Main Idea:

    The kth smallest element must be in the upper left region, because rows and columns are sorted in ascending order. Then we add possible elements to a list, in which the kth smallest element is the answer.

    Code:

    class Solution(object):
        def kthSmallest(self, matrix, k):
            res=[]
            res+=[matrix[i][j] for i in xrange(0,len(matrix)) for j in xrange(0,len(matrix)) if (i+1)*(j+1)<=k]
            return sorted(res)[k-1]

  • 0
    O

    Equivalent 1-liner:

    return sorted(n for i, row in enumerate(matrix) for j, n in enumerate(row) if (i+1)*(j+1)<=k)[k-1]
    

    Actually, it's even faster without the filter if (i+1)*(j+1)<=k:

    return sorted(n for row in matrix for n in row)[k-1]
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.