I know this has been asked before but this question is about my specific code. I am trying to do a psuedo QuickSelect algorithm where I compare k to the midpoint of a sub interval of a sorted matrix.
I keep getting a timeout error.
Here is the matrix:
matrix = [
[ 1, 5, 9],
[10, 11, 13],
[12, 13, 15]
k = 8
def kthSmallest(self, matrix, k):
:type matrix: List[List[int]]
:type k: int
return self.matrixRecur(matrix, (0, 0), (len(matrix) - 1, len(matrix) - 1), k)
def matrixRecur(self, splicedMatrix, left, right, k):
start_row, start_col = left
end_row, end_col = right
mid_row = (start_row + end_row)/2
mid_col = (start_col + end_col)/2
i = start_row
j = start_col
lcount = 0
while(not (i == mid_row and j == mid_col)):
if j < len(splicedMatrix):
j += 1
j = 0
i += 1
lcount += 1
if k == lcount:
elif k < lcount:
return self.matrixRecur(splicedMatrix, (start_row, start_col), (mid_row, mid_col), k)
return self.matrixRecur(splicedMatrix, (mid_row, mid_col + 1), (end_row, end_col), k-lcount)
Your above approach will not work. As your matrix is row and column wise sorted. Consider the matrix like below
10, 20, 30, 40 15, 25, 35, 45 24, 29, 37, 48 32, 33, 39, 50
Your approach will fail in this case. You are getting time out because you are traversing the whole 2D matrix. Worst case time complexity would be
O(mn) (m and n are respectively number of rows and columns).
You can use a min-heap to solve this problem.
1. Build a min heap of first row elements. A heap entry also stores row number and column number. 2. for(int i=0;i<k;i++) Get minimum element (or root) from min heap. Find row number and column number of the minimum element. Replace root with the next element from same column and min-heapify the root. 3. Return the last extracted root.
Time complexity :
O(n + kLogn)
Source : Kth smallest in 2D matrix