Kth Smallest Element of a Matrix of given dimensions filled with product of indices | Function that returns true if the count of elements is less than mid ; To store count of elements less than mid ; Loop through each row ; Count elements less than mid in the ith row ; Function that returns the Kth smallest element in the NxM Matrix after sorting in an array ; Initialize low and high ; Perform binary search ; Find the mid ; Check if the count of elements is less than mid ; Return Kth smallest element of the matrix ; Driver Code
def countLessThanMid ( mid , N , M , K ) : NEW_LINE INDENT count = 0 NEW_LINE for i in range ( 1 , min ( N , mid ) + 1 ) : NEW_LINE INDENT count = count + min ( mid // i , M ) NEW_LINE DEDENT if ( count >= K ) : NEW_LINE INDENT return False NEW_LINE DEDENT else : NEW_LINE INDENT return True NEW_LINE DEDENT DEDENT def findKthElement ( N , M , K ) : NEW_LINE INDENT low = 1 NEW_LINE high = N * M NEW_LINE while ( low <= high ) : NEW_LINE INDENT mid = low + ( high - low ) // 2 NEW_LINE if ( countLessThanMid ( mid , N , M , K ) ) : NEW_LINE INDENT low = mid + 1 NEW_LINE DEDENT else : NEW_LINE INDENT high = mid - 1 NEW_LINE DEDENT DEDENT return high + 1 NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT N = 2 NEW_LINE M = 3 NEW_LINE K = 5 NEW_LINE print ( findKthElement ( N , M , K ) ) NEW_LINE DEDENT