educative.io

Alternative Solution with O(k) time complexity

Courses
,
#1

Can you help me validate this solution?
I think this is a valid solution, which should solve the problem in O(K) time and O(1) space:

def find_Kth_smallest(matrix, k):

  number = -1

  counter = 0

  for i in range(len(matrix[0])):

    for j in range(len(matrix)):

      counter += 1

      if counter == k:

        return matrix[j][i] 

  # TODO: Write your code here

  return number

def main():

  print("Kth smallest number is: " +

        str(find_Kth_smallest([[2, 6, 8], [3, 7, 10], [5, 8, 11]], 1)))

  print("Kth smallest number is: " +

        str(find_Kth_smallest([[2, 6, 8], [3, 7, 10], [5, 8, 11]], 2)))

  print("Kth smallest number is: " +

        str(find_Kth_smallest([[2, 6, 8], [3, 7, 10], [5, 8, 11]], 3)))

  print("Kth smallest number is: " +

        str(find_Kth_smallest([[2, 6, 8], [3, 7, 10], [5, 8, 11]], 4)))

  print("Kth smallest number is: " +

        str(find_Kth_smallest([[2, 6, 8], [3, 7, 10], [5, 8, 11]], 5)))

  print("Kth smallest number is: " +

        str(find_Kth_smallest([[2, 6, 8], [3, 7, 10], [5, 8, 11]], 6)))

  print("Kth smallest number is: " +

        str(find_Kth_smallest([[2, 6, 8], [3, 7, 10], [5, 8, 11]], 7)))

  print("Kth smallest number is: " +

        str(find_Kth_smallest([[2, 6, 8], [3, 7, 10], [5, 8, 11]], 8)))

  print("Kth smallest number is: " +

        str(find_Kth_smallest([[2, 6, 8], [3, 7, 10], [5, 8, 11]], 9)))

main()

What do you think?
Thanks,
Riccardo

#2

Hi @Riccardo. Sorry for the very late reply. This solution is not completely correct. You solution will not work in some cases. For example: print("Kth smallest number is: " + str(find_Kth_smallest( [ [2, 6, 8], [7, 9, 10], [11, 12, 13]], 3))). The 3rd smallest number is 7 but your solution is returning 11.

Happy Learning :smiley:

1 Like