Search in 2D Matrix in DSA Python

Mental Model

We look for a number in a grid where each row and column is sorted, moving step by step to find it quickly.

Analogy: Imagine searching for a book in a library where shelves are sorted by author and books on each shelf are sorted by title. You start at the top-right corner and decide to move left or down depending on the book you want.

Matrix:
1  4  7  11
2  5  8  12
3  6  9  16
10 13 14 17

Start at top-right corner:
1   4   7  [11↑]
2   5   8   12
3   6   9   16
10  13  14  17

Dry Run Walkthrough

Input: matrix = [[1,4,7,11],[2,5,8,12],[3,6,9,16],[10,13,14,17]], target = 5

Goal: Find if the target number 5 exists in the matrix.

Step 1: Start at top-right element (11). Compare 11 with 5.

Position at 11 (top-right corner).

Why: We start here because it helps decide whether to move left or down.

Step 2: Since 11 > 5, move left to 7.

Matrix position now at 7 (row 0, col 2).

Why: Moving left decreases the number, getting closer to 5.

Step 3: Compare 7 with 5. Since 7 > 5, move left to 4.

Matrix position now at 4 (row 0, col 1).

Why: Still too big, so move left again.

Step 4: Compare 4 with 5. Since 4 < 5, move down to 5.

Matrix position now at 5 (row 1, col 1).

Why: Moving down increases the number, trying to reach 5.

Step 5: Compare 5 with 5. Found the target!

Position at 5 (row 1, col 1).

Why: Target found, search ends.

Result:

5 found at position (1, 1) in the matrix.

Annotated Code

DSA Python

class Solution:
    def searchMatrix(self, matrix: list[list[int]], target: int) -> bool:
        if not matrix or not matrix[0]:
            return False
        rows, cols = len(matrix), len(matrix[0])
        r, c = 0, cols - 1  # start top-right
        while r < rows and c >= 0:
            if matrix[r][c] == target:
                return True
            elif matrix[r][c] > target:
                c -= 1  # move left
            else:
                r += 1  # move down
        return False

# Driver code
matrix = [
    [1, 4, 7, 11],
    [2, 5, 8, 12],
    [3, 6, 9, 16],
    [10, 13, 14, 17]
]
target = 5
sol = Solution()
found = sol.searchMatrix(matrix, target)
print(f"{target} found: {found}")

r, c = 0, cols - 1 # start top-right

Initialize pointers at top-right corner to start search.

while r < rows and c >= 0:

Continue search while pointers are inside matrix bounds.

if matrix[r][c] == target:

Check if current element is the target.

elif matrix[r][c] > target:

If current element is bigger, move left to smaller elements.

else:

If current element is smaller, move down to bigger elements.

Output

5 found: True

Complexity Analysis

Time: O(m + n) because we move at most m times down and n times left in the matrix.

Space: O(1) because we only use a few variables for pointers, no extra space.

vs Alternative: Compared to searching every element (O(m*n)), this method is much faster by skipping large parts of the matrix.

Edge Cases

Empty matrix or matrix with empty rows

Returns False immediately as there is nothing to search.

DSA Python

if not matrix or not matrix[0]:

Target smaller than smallest element or larger than largest element

Search ends quickly without finding target, returns False.

DSA Python

while r < rows and c >= 0:

Target is at the first element (top-left corner)

Search moves down from top-right until it reaches the target.

DSA Python

else: r += 1  # move down

When to Use This Pattern

When you see a sorted 2D matrix and need to find a value efficiently, use the top-right corner search pattern to eliminate rows or columns step by step.

Common Mistakes

Mistake: Starting search from top-left or bottom-left corner without adjusting logic.
Fix: Always start from top-right corner to use the property that moving left decreases and moving down increases values.

Mistake: Not checking matrix or row emptiness before search.
Fix: Add a guard clause to return False if matrix or first row is empty.

Summary

Searches a sorted 2D matrix for a target by moving left or down from the top-right corner.

Use when matrix rows and columns are sorted and you want faster than brute force search.

Start at top-right and move left if too big, down if too small to find target efficiently.

Practice

1. What is the main idea behind searching an element in a 2D matrix where each row and column is sorted in ascending order?

easy

A. Start from top-right corner and move left or down based on comparison

B. Start from bottom-left corner and move left or down based on comparison

C. Search each element one by one from left to right, top to bottom

D. Use binary search on each row independently

Solution

1. Step 1: Understand matrix properties and use top-right corner

   Each row and column is sorted ascending, so top-right element is largest in its row and smallest in its column. If target is less than current element, move left; if greater, move down.

2. Final Answer:

   Start from top-right corner and move left or down based on comparison -> Option A

3. Quick Check:

   Top-right start = efficient search [OK]

Hint: Start at top-right to decide direction quickly [OK]

Common Mistakes:

• Starting from bottom-left without adjusting logic
• Searching all elements linearly
• Using binary search on each row without considering columns

2. Which of the following Python code snippets correctly initializes a 2D matrix named matrix with 3 rows and 4 columns filled with zeros?

easy

A. matrix = [[0]*4]*3

B. matrix = [[0]*3 for _ in range(4)]

C. matrix = [0]*3*[0]*4

D. matrix = [[0 for _ in range(4)] for _ in range(3)]

Solution

1. Step 1: Understand list comprehension for 2D matrix and check options

   Use nested list comprehension [[0 for _ in range(4)] for _ in range(3)] to create independent 3 rows with 4 zeros each. A shares references, B wrong dimensions, C syntax invalid.

2. Final Answer:

   matrix = [[0 for _ in range(4)] for _ in range(3)] -> Option D

3. Quick Check:

   Nested list comprehension = correct matrix init [OK]

Hint: Use nested list comprehension for independent rows [OK]

Common Mistakes:

• Using [[0]*4]*3 causes shared references
• Multiplying lists incorrectly
• Swapping rows and columns in comprehension

3. What will be the output of the following code?

matrix = [
  [1, 3, 5, 7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]
target = 3

row, col = 0, len(matrix[0]) - 1
found = False
while row < len(matrix) and col >= 0:
    if matrix[row][col] == target:
        found = True
        break
    elif matrix[row][col] > target:
        col -= 1
    else:
        row += 1
print(found)

medium

A. IndexError

B. False

C. True

D. SyntaxError

Solution

1. Step 1: Trace starting position and comparisons until target found

   Start at top-right: matrix[0][3] = 7 > 3, move left to col=2; matrix[0][2] = 5 > 3, move left col=1; matrix[0][1] = 3 == target, found = True.

2. Final Answer:

   True -> Option C

3. Quick Check:

   Found target 3 = True [OK]

Hint: Start top-right, move left/down until found or out of bounds [OK]

Common Mistakes:

• Confusing row and column indices
• Not updating row or col correctly
• Assuming linear search needed

4. The following code is intended to search for a target in a sorted 2D matrix but does not work correctly. What is the error?

def search_matrix(matrix, target):
    row = 0
    col = len(matrix[0])
    while row < len(matrix) and col >= 0:
        if matrix[row][col] == target:
            return True
        elif matrix[row][col] > target:
            col -= 1
        else:
            row += 1
    return False

medium

A. col should start at len(matrix[0]) - 1, not len(matrix[0])

B. row should start at len(matrix) - 1

C. The while loop condition should use 'or' instead of 'and'

D. The function should return null instead of false

Solution

1. Step 1: Check initial column index and correct start

   col is set to len(matrix[0]) which is out of range (indexing starts at 0). It should be len(matrix[0]) - 1 to start at last valid column index.

2. Final Answer:

   col should start at len(matrix[0]) - 1, not len(matrix[0]) -> Option A

3. Quick Check:

   Index out of range fix = col start - 1 [OK]

Hint: Start col at last index: length minus one [OK]

Common Mistakes:

• Starting col at length causes IndexError
• Changing row start incorrectly
• Using wrong loop condition

5. Given a 2D matrix where each row and column is sorted ascending, write a function to count how many times a target number appears. Which approach is most efficient?

hard

A. Traverse entire matrix and count matches (O(m*n))

B. Use binary search on each row and sum counts (O(m*log n))

C. Start from top-right and move left/down counting matches (O(m+n))

D. Flatten matrix to 1D list and use built-in count method

Solution

1. Step 1: Analyze time complexities and correct approach

   Full traversal O(m*n), top-right single pass misses duplicates off the path, flatten O(m*n); binary search on each row finds leftmost/rightmost target positions to compute count per row, total O(m*log n) efficient and correct.

2. Final Answer:

   Use binary search on each row and sum counts (O(m*log n)) -> Option B

3. Quick Check:

   Binary per row = efficient count [OK]

Hint: Binary search range in each row [OK]

Common Mistakes:

• Using full traversal wasting time
• Flattening matrix loses sorted structure
• Top-right movement misses off-path duplicates