kth smallest element sorted matrix using QuickSelect
<p>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. </p>

<p>I keep getting a timeout error.</p>

<p>Here is the matrix:</p>

<pre><code>matrix = [
   [ 1,  5,  9],
   [10, 11, 13],
   [12, 13, 15]
],
k = 8
</code></pre>

<p>Here is my code:</p>

<pre><code>def kthSmallest(self, matrix, k):
    """
    :type matrix: List[List[int]]
    :type k: int
    :rtype: int
    """

    return self.matrixRecur(matrix, (0, 0), (len(matrix) - 1, len(matrix[0]) - 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 &lt; len(splicedMatrix[0]):
            j += 1
        else:
            j = 0
            i += 1
        lcount += 1
    if k == lcount:
       return splicedMatrix[mid_row][mid_col]
    elif k &lt; lcount:
        return self.matrixRecur(splicedMatrix, (start_row, start_col), (mid_row, mid_col), k)
    else:
        return self.matrixRecur(splicedMatrix, (mid_row, mid_col + 1), (end_row, end_col), k-lcount)
</code></pre>

<p>I pass in tuples to <code>matrixRecur</code> which contain the <code>(row, col)</code> of the endpoints of the interval. So, if I want to search the whole matrix, I pass <code>(0, 0)</code> and <code>(n, n)</code>. <code>matrixRecur</code> will look at a subinterval, determine the midpoint based on the row col numbers of the endpoints, count the number of elements less than the midpoint, compare it to <code>k</code>. If <code>k</code> is less than the number of elements less than the midpoint (<code>lcount</code>), then the kth smallest element is within the left interval because there are at most <code>lcount</code> elements less than the midpoint and <code>k</code> &lt; <code>lcount</code>. </p>

<p>I am running this on an interview question site and the site continues to tell me my code times out. I am not seeing why. </p>