educative.io

Complexity of kth smallest element in sorted matrix

Courses
,
#1

The provided solution has:

  1. time complexity of O((n+k)logn)
  2. space complexity of O(n)

In the case where k < n, in the first pass, do we need to store n elements, or can we just store k? It seems we’ll never use the elements beyond the first k rows. Could we edit line 7 to: for index in range(min(row_count, k)):? And store just m = min(n, k) elements:

  1. time complexity of O(klogm)
  2. space complexity of O(m)

Course: Grokking Coding Interview Patterns in Python - Learn Interactively
Lesson: Solution: Kth Smallest Element in a Sorted Matrix - Grokking Coding Interview Patterns in Python

1 Like
#2

Hello @Isaac_Haseley,

Your observation is correct, we can further optimize our approach to store only the minimum of any (elements in matrix, or k). There might not be any need to specifically iterate over the entire matrix and populate all elements in min_numbers. We’ll work on improving the solution and explanation of this problem and will let you know once the updated version is live. Thanks!

Happy learning!

1 Like