DSA sheet · Binary Search · 2D matrix + binary search on answer

Kth Smallest in Sorted Matrix

The third 2D-matrix question, and it joins two earlier ideas. From Problem 13 we take the staircase walk, which here counts how many numbers are ≤ some value instead of searching for one. From the binary-search-on-answer problems (14–21) we take the habit of binary searching over possible answers, not over positions. The teacher goes step by step: brute force (flatten and sort) → try every value from smallest to biggest with a count function → replace that loop with binary search. She says plainly that if binary search on answer is new to you, watch those videos first. Part 0 below recaps it so this page stands alone.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the conditions from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · What you must know before starting
• Part A · Brute force: flatten and sort
• Part B · Better: try every value with a staircase count
• Part C · Optimal: binary search on the answer
• Part D · Revision page

Part 0 · Before starting

Why binary search works

Binary search needs a sorted order, or more generally a yes/no question whose answers go no, no, …, no, yes, yes, …, yes as you move right. Then one check at the middle tells you which half to throw away. low and high mark what's still possible, mid is the middle, and we stop when low > high.

mid = low + (high - low) // 2

In Java/C++, low + high can be bigger than the largest int and overflow (wrap to a negative number). Writing low + (high - low) // 2 avoids building that big sum. The teacher uses this safe form here. Python ints never overflow, so both forms work in Python. Also, // rounds down (towards −∞), which keeps mid between low and high even when the values are negative.

The "binary search on answer" pattern

1. Answer range. Don't search positions. Ask: "what is the smallest the answer could be, and the biggest?" Here the answer is a value in the matrix, so it lies between the smallest value matrix[0][0] and the biggest matrix[n-1][n-1].
2. A yes/no check for a guess. For a guess x, ask: "are at least k numbers in the matrix ≤ x?" Call the count count(x).
3. Monotonic (only goes one way): if x makes count(x) ≥ k true, then any bigger x also does, because a bigger x can only include more numbers. So over the range, the check looks like no no no yes yes yes.
4. Which side to keep. We want the first yes: the smallest x with count(x) ≥ k. If mid says no (count < k) → the answer is bigger → low = mid + 1. If mid says yes → mid might be the answer, but maybe something smaller is too → high = mid - 1. When the loop ends, low is the first yes.

Matrix words

• An n × n matrix has n rows and n columns. matrix[r][c] = row r, column c, from 0.
• Sorted row-wise and column-wise: each row grows left → right, each column grows top → bottom (non-decreasing, so repeats are allowed).
• Kth smallest: write all n² numbers in sorted order (repeats included) and take the k-th one (1-based). With repeats like 1, 2, 2, 3, the 2nd and 3rd smallest are both 2.

The example matrix used on this page

          c0   c1   c2   c3
   r0  [  16   28   60   64 ]
   r1  [  22   41   63   80 ]
   r2  [  27   50   66   82 ]
   r3  [  36   78   83   94 ]

   sorted: 16 22 27 28 36 41 50 60 63 64 66 78 80 82 83 94

This is the teacher's 4 × 4 example. Not every cell is readable in the video, so a few inner values are filled in here so that every fact she states holds: the corners 16, 36, 64, 94; column 0 is 16, 22, 27, 36; row 0 starts 16, 28, 60; the counts for 16, 23, 27 and 30 match hers, and the 10th smallest is 64.

Part A · Brute force: flatten and sort

LeetCode 378 · Kth Smallest Element in a Sorted Matrix

1The question in simple words

You get an n × n matrix where every row and every column is sorted in non-decreasing order, and a number k. Return the k-th smallest number of the whole matrix (counting repeats, so it's the k-th in sorted order, not the k-th distinct).

Example (LeetCode): [[1,5,9],[10,11,13],[12,13,15]], k = 8 → sorted is 1 5 9 10 11 12 13 13 15 → the 8th is 13. On our 4 × 4 matrix with k = 3 → 27.

2What the constraints tell us

• n ≤ 300 on LeetCode. The teacher reads it as 500, giving 500 × 500 = 25 × 10⁴ cells. Either way, at most a few hundred thousand cells.
• 1 ≤ k ≤ n², so the k-th smallest always exists.
• Values: the teacher reads them as 1 … 10⁴. Careful: the LeetCode statement allows −10⁹ … 10⁹. This doesn't matter for Parts A and C, but it matters a lot for Part B (see there).
• She reads the constraints for two reasons: to see which pattern fits, and to see how far we need to optimise.

3Intuition

Forget the matrix is sorted. Pour all numbers into one list, sort it, and pick position k − 1 (lists start at index 0).

4Building the logic: what the matrix does and doesn't tell us

The teacher first looks at what we know for sure from the sorting:

• The smallest number is always the top-left, matrix[0][0] (16). So k = 1 → 16.
• The biggest is always the bottom-right (94). So whatever we return lies between 16 and 94.
• But the 2nd smallest could be either neighbour of 16: right (28) or down (22). Here it's 22, but 28 could have been 17 and the matrix would still be sorted. So we must compare both.
• The 3rd smallest could be any of 28, 41 or 27 (the "frontier" grows). The order between rows isn't fixed, which is why we can't just read the k-th number off the grid.

The simplest fix: flatten and sort.

5Approach steps

1. Put every number in one list.
2. Sort it.
3. Return values[k - 1].

6Code (Python)

class Solution:
    def kthSmallest(self, matrix, k):
        values = []
        for row in matrix:
            for v in row:
                values.append(v)
        values.sort()
        return values[k - 1]          # k is 1-based, lists are 0-based

7Code line by line

8Dry run (k = 3)

9Complexity & remember

• Time O(N log N) with N = n² numbers, i.e. O(n² log n).
• Space O(n²): the copied list.

Slow, and it uses extra space. What if the interviewer says "no extra space, work in the matrix itself"? And since the matrix is already sorted, they expect us to use that with binary search.

Part B · Try every value, with a staircase count

1The question

Same question, but now: no extra list, and use the sorted rows and columns.

2What the constraints tell us

• The answer is between matrix[0][0] and matrix[n-1][n-1]. With the teacher's value range (up to 10⁴), there are at most 10⁴ values to try.
• Each count costs about 2n ≤ 2 × 500 = 10³ steps. So 10⁴ × 10³ = 10⁷ in total: under 10⁸, so it passes, just a bit slowly.
• But with LeetCode's range of −10⁹ … 10⁹, there could be about 2 × 10⁹ values to try → far too slow. So treat this part as the stepping stone to Part C, not as the final answer.

3Intuition: a "how many are ≤ x?" game

The teacher frames it as a game. I tell you a number x. You tell me how many numbers in the matrix are ≤ x.

• x = 16 → just 16 → 1.
• x = 23 → 16 and 22 → 2.
• x = 27 → 16, 22, 27 → 3.

Now try x = 16, 17, 18, … in order. The first x whose count reaches k is the k-th smallest. For k = 3: 16 to 21 give 1, 22 to 26 give 2, and 27 gives 3 → answer 27.

4Building the count function from examples

Where to start: the bottom-left cell (36)

This is the Problem 13 corner idea again. At 36, smaller numbers are up and bigger numbers are right, one direction each. So the code always knows where to go.

• 16 (top-left): want bigger → two choices (right or down). Want smaller → nowhere. Can't use.
• 94 (bottom-right): want smaller → two choices. Want bigger → nowhere. Can't use.
• 64 (top-right): smaller is left, bigger is down. It works for moving. The teacher prefers 36 because counting from the bottom-left adds up the "small" side directly (see the doubt below).
• 36 (bottom-left): chosen.

Example: count(16) → too big means go up

At 36: 36 > 16. Going right only gives bigger numbers, so go up (row − 1). 27 > 16 → up. 22 > 16 → up. 16 ≤ 16 ✓. Now we're in row 0. Since the column is sorted, everything above this cell (nothing here) is also ≤ 16. So this column adds row + 1 = 0 + 1 = 1 number.

Example: count(27) → why we add row + 1

At 36 > 27 → up. At 27 ≤ 27 ✓, in row 2. The column is sorted top to bottom, so 27 and everything above it (22, 16) are ≤ 27. That's rows 0, 1, 2 → row + 1 = 3 numbers from this column in one go. No need to walk up and check them one by one.

Example: count(30) → why we can't stop after the first "≤"

At 36 > 30 → up. At 27 ≤ 30 → count += 3. If we returned now we'd say 3, but 28 (column 1) is also ≤ 30. Other columns can still have small numbers, so we must move right and keep counting:

          c0      c1      c2     c3
   r0  [  16    [28]5   [60]6    64 ]
   r1  [  22    [41]4    63      80 ]
   r2  [ [27]2  [50]3    66      82 ]
   r3  [ [36]1   78      83      94 ]

   [x]k = k-th cell visited for count(30)

Boundaries: row only goes down (it can reach −1) and col only goes up (it can reach n). So the loop runs while row >= 0 and col < n.

What the count function returns

The teacher has it return True when count ≥ k, not "== k". With repeated values, the count can jump past k in one step (for [[1,2],[2,3]] and k = 2: count(1) = 1, count(2) = 3). So we look for "at least k", never "exactly k". The first x where it becomes True is the answer.

def count_top_right(matrix, x):
    n = len(matrix)
    row, col, count = 0, n - 1, 0
    while row < n and col >= 0:
        if matrix[row][col] <= x:
            count += col + 1          # this cell and everything left of it
            row += 1
        else:
            col -= 1
    return count

5Approach steps

1. low = matrix[0][0], high = matrix[n-1][n-1].
2. For x = low, low + 1, …, high: if count(x) >= k, return x.
3. count(x): start at bottom-left. Value > x → up. Else → add row + 1 and go right. Stop when outside.

6Code (Python)

class Solution:
    def kthSmallest(self, matrix, k):
        n = len(matrix)
        low, high = matrix[0][0], matrix[n - 1][n - 1]
        for x in range(low, high + 1):
            if self.enough(matrix, x, k):
                return x                      # first x with at least k numbers <= x
        return high

    def enough(self, matrix, x, k):
        n = len(matrix)
        row, col = n - 1, 0                   # bottom-left corner
        count = 0
        while row >= 0 and col < n:
            if matrix[row][col] > x:
                row -= 1                      # too big: go up
            else:
                count += row + 1              # this cell and all above it are <= x
                col += 1                      # next column
        return count >= k

7Code line by line

8Dry run (k = 3)

That's 12 calls of the count function before we hit 27. With a wide value range this loop would make a huge number of calls, and Part C cuts them down.

9Complexity & remember

One count costs at most 2n − 1 cells

Each step goes up one row or right one column. There are n rows and n columns, so at most about 2n steps, not n². The longest walk on our matrix is for x = 64 (k = 10):

          c0      c1      c2      c3
   r0  [  16      28      60     [64]7 ]
   r1  [  22      41     [63]5   [80]6 ]
   r2  [  27     [50]3   [66]4    82   ]
   r3  [ [36]1   [78]2    83      94   ]

   7 cells = 2n − 1 for n = 4,  count = 4 + 3 + 2 + 1 = 10

• Time O((high − low + 1) × n). With her numbers: 10⁴ values × about 10³ steps = 10⁷. Passes, but slowly.
• Space O(1): no copy of the matrix.

Part C · Optimal: binary search on the answer

1The question

Same. Part B tried 16, 17, 18, … one by one. Can we skip most of them?

2What the constraints tell us

• The value range is the search space. Binary search over it takes about log₂(range) rounds.
• Her numbers: log₂(10⁴) ≈ 14 rounds (2¹⁰ ≈ 10³, so 10⁴ needs a bit more than 13). Instead of 10,000 tries we make 14.
• LeetCode's full range: log₂(2 × 10⁹) ≈ 31 rounds. Still tiny. This is why Part C is the one to submit.

3Intuition

The values 16 … 94 are in order, and the answer to "count(x) ≥ k?" is no for a while and then yes forever after (Part 0). So we don't need to walk from the left. Jump to the middle value, count, and throw away half of the range.

• Mid value says "I have 4 numbers ≤ me", but we want the 3rd. 4 ≥ 3 → mid is too big or just right → look left (smaller values).
• Mid value 22 says "only 2 numbers ≤ me". 2 < 3 → the 3rd smallest must be bigger → look right.

4Building the conditions

(While speaking she says "greater than k → left" for both cases for a moment, but the code is clear: less than k → right, otherwise → left.)

Why return low and not high?

The teacher explains it through the moment the two pointers cross. Think about what each pointer means while the loop runs:

• Everything below low has been tested (directly or by halving) and said no.
• Everything above high has said yes.

The loop ends when low = high + 1. Then high sits on the last "no" (a value where low used to be checked and failed), and low sits on the first "yes". The first yes is the answer, so return low. In her small picture: just before crossing, low was at a value that wasn't good enough, then low moved up past high. high ended on that "not good enough" spot, which can't be the answer.

5Approach steps

1. low = matrix[0][0], high = matrix[n-1][n-1].
2. While low <= high: mid = low + (high - low) // 2, c = count(mid).
3. c < k → low = mid + 1. Else → high = mid - 1.
4. Return low.

6Code (Python)

class Solution:
    def kthSmallest(self, matrix, k):
        n = len(matrix)
        low, high = matrix[0][0], matrix[n - 1][n - 1]
        while low <= high:
            mid = low + (high - low) // 2
            if self.count_le(matrix, mid) < k:
                low = mid + 1                 # not enough: answer is bigger
            else:
                high = mid - 1                # enough: try smaller
        return low                            # first value with count >= k

    def count_le(self, matrix, x):            # how many numbers are <= x
        n = len(matrix)
        row, col = n - 1, 0                   # bottom-left corner
        count = 0
        while row >= 0 and col < n:
            if matrix[row][col] > x:
                row -= 1
            else:
                count += row + 1
                col += 1
        return count

7Code line by line

8Dry run (k = 3, answer 27)

6 rounds of counting instead of 12 in Part B. The gap grows hugely with a wider range: about 14 rounds instead of 10,000 for her range.

9Complexity & remember

• Time O(n × log(high − low)): about log₂(range) rounds, each one a 2n-step count. Her numbers: 14 × 1000 ≈ 1.4 × 10⁴, versus 10⁷ for Part B.
• Space O(1).

Part D · Revision page

matrix = [[16, 28, 60, 64],
          [22, 41, 63, 80],
          [27, 50, 66, 82],
          [36, 78, 83, 94]]
s = Solution()
print(s.kthSmallest(matrix, 3))                                # 27
print(s.kthSmallest(matrix, 10))                               # 64
print(s.kthSmallest([[1, 5, 9], [10, 11, 13], [12, 13, 15]], 8))  # 13
print(s.kthSmallest([[-5]], 1))                                # -5
print(s.kthSmallest([[1, 2], [2, 3]], 3))                      # 2 (repeats)

Based on this video: Kth Smallest Element in a Sorted Matrix | Binary Search on Answer