DSA sheet · Binary Search · Search in a 2D matrix pattern

Search a 2D Matrix II

This is the second question of the 2D-matrix pattern, and it's a trap question. The matrix is sorted along every row and every column, so your hand reaches for binary search. The teacher shows why binary search does not work here, and then builds the staircase search: start at a corner where "bigger" and "smaller" point in different directions, and step left or down until you find the target. It runs in O(m + n). She says interviewers like this one because it shows whether you understood the previous problem or just memorised its code. She also explains which corner you can start from and why, which is a favourite follow-up question.

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: look at every cell
• Part B · Why the binary search from Problem 12 breaks here
• Part C · Staircase search from the top-right corner
• Part D · Staircase from the bottom-left corner (her homework)
• Part E · Revision page

Part 0 · Before starting

Binary search in one paragraph

Binary search works when looking at one position lets you say "the answer is definitely not on this side". That's true for a sorted array, or any yes/no question whose answers go "no … no, yes … yes" in order. We keep low and high (the first and last positions still possible), look at the middle mid, and throw away half with low = mid + 1 or high = mid - 1. Each step halves the work, so it takes O(log n) steps.

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

In Java/C++, (low + high) can go past the largest int and wrap around to a negative number (overflow). low + (high - low) // 2 gives the same middle without ever making that big sum. Python ints never overflow, so in Python both forms are fine, but the safe form is a good habit.

Matrix words

• m × n matrix = m rows (horizontal), n columns (vertical). matrix[r][c] is row r, column c, both from 0.
• Rows: len(matrix). Columns: len(matrix[0]).
• Row-wise sorted: each row grows left → right. Column-wise sorted: each column grows top → bottom.
• A neighbour of a cell is the cell directly up, down, left or right of it.

What we learned in Problem 12 (LeetCode 74)

There, a third property was given: each row's first value is bigger than the previous row's last value. That made the whole matrix one sorted line when read row by row, so we could binary search the rows and then the row. Keep that in mind: this problem doesn't have that property.

Part A · Brute force: look at every cell

LeetCode 240 · Search a 2D Matrix II

1The question in simple words

Write an efficient function that tells whether target is in an m × n matrix. The matrix has two properties:

1. Every row is sorted in ascending order, left to right.
2. Every column is sorted in ascending order, top to bottom.

          c0  c1  c2  c3  c4
   r0  [   1   4   7  11  15 ]
   r1  [   2   5   8  12  19 ]
   r2  [   3   6   9  16  22 ]
   r3  [  10  13  14  17  24 ]
   r4  [  18  21  23  26  30 ]

Example 1: target 5 → True. Example 2: target 20 → False.

2What the constraints tell us

• m and n go up to 300. So there are at most 300 × 300 = 9 × 10⁴ cells.
• The teacher's TLE rule of thumb: up to about 10⁸ simple operations is safe (sometimes only 10⁷ if each step does heavy work). Beyond that, expect TLE. 9 × 10⁴ is far below, so a linear scan would be accepted.
• Values and target can be from −10⁹ to 10⁹. We only compare numbers, never add them, so overflow isn't an issue.
• But the statement says "write an efficient algorithm". That's the interviewer telling you the linear scan isn't the answer they want.

3Intuition

Ignore every property. Look at every cell, one by one. If one equals target, say True.

4Building the logic

There's nothing to derive: two loops over rows and columns. It's correct for any matrix, sorted or not. That's exactly its weakness: it doesn't use either sorted property.

5Approach steps

1. For each row, for each value in the row: if it equals target → True.
2. After the loops → False.

6Code (Python)

class Solution:
    def searchMatrix(self, matrix, target):
        for row in matrix:
            for value in row:
                if value == target:
                    return True
        return False

7Code line by line

8Dry run

Target 5: row 0 checks 1, 4, 7, 11, 15 (no). Row 1 checks 2, then 5 → True after 7 looks. Target 20: all 25 cells are checked → False.

9Complexity & remember

• Time O(m·n), space O(1).

Part B · Why the binary search from Problem 12 breaks

1The question

Same problem. The matrix is sorted, and "sorted" makes us think of binary search. Can we reuse Problem 12's plan (binary search for the valid row, then binary search in it)?

2Constraints

Same as Part A. The thing to look at here is not the size but the properties: only two are given, and the third one from Problem 12 is missing.

3Intuition

Problem 12's row search worked only because each row started after the previous row ended. Comparing with one row's first value then told us about all the rows above and below. Without that guarantee, a row's first value tells us nothing about the rows above it.

Reason 1: comparing with a row's first value gives a wrong answer

Say target = 4, and we look at row 1, which starts with 2. In Problem 12, "4 > 2" would mean "4 is in this row or below". Here, that's false: 4 is in row 0, column 1, above row 1. Row 0 ends at 15, which is bigger than row 1's first value 2, so the rows overlap. A binary search that went down from row 1 would never find the 4.

          c0  c1  c2  c3  c4
   r0  [   1   4   7  11  15 ]    ← 4 is here, ABOVE row 1
   r1  [   2   5   8  12  19 ]    ← "4 > 2, so go down?"  wrong ✗

It doesn't matter whether you compare with the first or the last value of a row. Without the third property, neither one is safe.

Reason 2: "open it up" and see if it's sorted

The test from the last video: write the rows one after another and check whether the line is sorted.

Opened up either way, it's not one sorted line. So there's no single sorted array to binary search, and the Problem 12 logic can't be used.

4So what's left?

Not linear (too slow for the interviewer), not binary search (doesn't apply). But the matrix is sorted, and we should still use that. The trick is to find a cell where one comparison tells us exactly one direction to move. That's Part C.

5–8 (nothing to code here)

This part is the "why not". There's no code to run, because the idea is wrong. Remember the two reasons in case an interviewer asks.

9Remember

Part C · Staircase search from the top-right corner

1The question

Same: is target in the row-sorted and column-sorted matrix? Return True/False. Do better than O(m·n).

2What the constraints tell us

• m, n ≥ 1, so the matrix always has at least one cell, and matrix[0] exists.
• We will move one row or one column per step, so we will take at most about m + n ≤ 600 steps. That's tiny.

3Intuition: stand where "bigger" and "smaller" point different ways

Picture yourself standing on a cell and comparing it with the target. The value is either too small (you want something bigger) or too big (you want something smaller). The question is: from this cell, is there exactly one direction for "bigger" and exactly one for "smaller"?

Try the top-left cell (1)

Target 3. 1 < 3, so we want bigger. But right (4) is bigger and down (2) is bigger too. Two choices. Which one? From code, we can't tell. Stuck.

Try 4, then 7, then 11 (the top row)

Target 7 while standing on 4: we want bigger, but right and down are both bigger. Same problem for 7 and 11. (Don't think "I can see 7 is just to the right". Think like code: the code can't see, it can only compare the current cell.)

Try the top-right cell (15)

From 15: the only neighbours are left (11, smaller, because the row grows to the right) and down (19, bigger, because the column grows downward). So:

• want smaller → the only way is left
• want bigger → the only way is down

Exactly one path for each case. Now the code can decide. And this stays true as we walk: we only ever move left or down, so everything above us and to our right has already been ruled out.

4Building the conditions from examples

Example: target 4 → value too big → move left (column − 1)

At 15: 15 > 4. Going down only gives bigger numbers, so we must go left. The row doesn't change, the column goes down by one.

At 11 (still > 4) → left. At 7 (> 4) → left. At 4 → it's equal.

Example: target 5 → value too small → move down (row + 1)

Same walk: 15 → 11 → 7 → 4. Now 4 < 5, so we want bigger. Left would only give smaller numbers (we just came from there and they were too big, and left of 4 is 1). So we go down. The column stays the same, the row increases. Down from 4 is 5 → equal → True.

Example: target 0 → walking off the edge

15 → 11 → 7 → 4 → 1 are all bigger than 0, so we keep going left. From 1 (column 0), c -= 1 makes c = -1. We've left the matrix. So the moves need a boundary check:

• going left, c can become −1 → keep looping only while c >= 0.
• going down, r can become m → keep looping only while r < m.

Put all the rules inside while r < m and c >= 0:. If the loop ends, we walked off the matrix without finding the target → return False.

Why if / elif / else and not three separate ifs?

The teacher points out that after c -= 1 makes c = −1, a separate if right below would run straight away, before the while gets a chance to check the boundary. With elif/else, exactly one branch runs per loop, and then the loop condition is checked again.

5Approach steps

1. m = len(matrix), n = len(matrix[0]).
2. Start at the top-right corner: r = 0, c = n - 1.
3. While r < m and c >= 0: equal → True · bigger than target → c -= 1 (left) · else → r += 1 (down).
4. Loop ended → False.

6Code (Python)

class Solution:
    def searchMatrix(self, matrix, target):
        m = len(matrix)
        n = len(matrix[0])
        r, c = 0, n - 1                  # top-right corner

        while r < m and c >= 0:          # still inside the matrix
            if matrix[r][c] == target:
                return True
            elif matrix[r][c] > target:
                c -= 1                   # too big: whole column is too big, go left
            else:
                r += 1                   # too small: rest of row is too small, go down
        return False

7Code line by line

8Dry run, step by step

Target 5 (her first example, found)

  1   4   7  11 15
  2   5   8  12  19
  3   6   9  16  22
 10  13  14  17  24
 18  21  23  26  30

  1   4   7 11  15
  2   5   8  12  19
  3   6   9  16  22
 10  13  14  17  24
 18  21  23  26  30

  1   4  7  11  15
  2   5   8  12  19
  3   6   9  16  22
 10  13  14  17  24
 18  21  23  26  30

  1  4   7  11  15
  2   5   8  12  19
  3   6   9  16  22
 10  13  14  17  24
 18  21  23  26  30

  1   4   7  11  15
  2  5   8  12  19
  3   6   9  16  22
 10  13  14  17  24
 18  21  23  26  30

Grey = thrown away. Each "left" drops a whole column, each "down" drops a whole row. (Target 4 is the same walk, stopping at step 4 with 4 == 4.)

Target 0 (not there, falls off the left edge)

Target 18 (her long example: a real staircase)

          c0    c1    c2    c3    c4
   r0      1     4     7    11   [15]1
   r1      2     5     8   [12]3 [19]2
   r2      3     6     9   [16]4  22
   r3     10    13    14   [17]5  24
   r4   [18]9 [21]8 [23]7 [26]6  30

   [x]k = the k-th cell we visit

The path goes down and left like the steps of a staircase, which is where the name comes from. Note this isn't "linear search": we never look at most of the cells.

9Complexity & remember

Time O(m + n)

The teacher works it out from three walks:

• Target 1: we go left along the top row only → about n steps (all columns).
• Target 30: we go down the last column only → about m steps (all rows).
• Target 18: we go down and left all the way across → 9 cells for a 5 × 5 matrix.

Why 9 and not 5 + 5 = 10? The corner cell where the path turns, (row 4, column 0) here, gets counted twice if you add "all rows" and "all columns". Each step drops one row or one column, and r can grow at most m − 1 times and c can shrink at most n − 1 times, so we visit at most m + n − 1 cells. In big-O that's O(m + n). Not logarithmic, because we never throw away half. We throw away one row or one column at a time.

Space O(1): just r and c.

Which cells can be the starting point? (interview question)

Part D · Staircase from the bottom-left corner

The teacher leaves this as homework: start from the other valid corner. Steps 1–2 are the same as Part C. Here is what changes.

3Intuition

At the bottom-left (18): up is smaller (column grows downward) and right is bigger (row grows to the right). So: too big → go up; too small → go right.

4Conditions

• Value > target: 18 is the biggest of what's left in its column → drop that row → r -= 1.
• Value < target: it's the smallest of what's left in its row → drop that column → c += 1.
• Boundaries flip: loop while r >= 0 and c < n.

5Approach steps

1. Start at r = m - 1, c = 0.
2. Equal → True. Bigger → up. Smaller → right.
3. Out of the grid → False.

6Code (Python)

class Solution:
    def searchMatrix(self, matrix, target):
        m, n = len(matrix), len(matrix[0])
        r, c = m - 1, 0                  # bottom-left corner
        while r >= 0 and c < n:
            if matrix[r][c] == target:
                return True
            elif matrix[r][c] > target:
                r -= 1                   # too big: go up
            else:
                c += 1                   # too small: go right
        return False

7What changes, line by line

8Dry run (target 5)

          c0    c1    c2    c3    c4
   r0      1     4     7    11    15
   r1      2    [5]5   8    12    19
   r2    [3]3  [6]4    9    16    22
   r3    [10]2  13    14    17    24
   r4    [18]1  21    23    26    30

   [x]k = the k-th cell we visit

9Complexity

Same: O(m + n) time, O(1) space.

Part E · Revision page

matrix = [[1, 4, 7, 11, 15],
          [2, 5, 8, 12, 19],
          [3, 6, 9, 16, 22],
          [10, 13, 14, 17, 24],
          [18, 21, 23, 26, 30]]
s = Solution()
print(s.searchMatrix(matrix, 5))    # True
print(s.searchMatrix(matrix, 20))   # False
print(s.searchMatrix(matrix, 18))   # True  (9 steps from top-right)
print(s.searchMatrix(matrix, 0))    # False (falls off the left)
print(s.searchMatrix([[-5]], -5))   # True

Based on this video: Search a 2D Matrix II | Staircase approach