Search in 2D Matrix in DSA Python - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to check if the target is in the first row of the matrix.

DSA Python

matrix = [[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]]
target = 3
if target in matrix[1]:
    print("Found")
else:
    print("Not Found")

Drag options to blanks, or click blank then click option'

A[-1]

B[1]

C[0]

D[2]

Attempts:

3 left

💡 Hint

Common Mistakes

Using matrix[1] or matrix[-1] instead of matrix[0].

Checking the whole matrix instead of a specific row.

The first row of the matrix is accessed by matrix[0]. Checking if the target is in this row helps find it quickly.

2fill in blank

medium

Complete the code to find the row where the target could be by comparing the last element of each row.

DSA Python

matrix = [[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]]
target = 13
row = 0
for i in range(len(matrix)):
    if matrix[i][-1] >= [1]:
        row = i
        break
print(row)

Drag options to blanks, or click blank then click option'

Atarget

Bmatrix[i][0]

Cmatrix[i][-1]

Di

Attempts:

3 left

💡 Hint

Common Mistakes

Comparing with the first element of the row instead of the target.

Using the index i instead of the target.

We compare the last element of each row with the target to find the row where the target could be.

3fill in blank

hard

Fix the error in the binary search code to correctly find the target in the selected row.

DSA Python

def binary_search(row, target):
    left, right = 0, len(row) - 1
    while left <= right:
        mid = (left + right) // 2
        if row[mid] == [1]:
            return True
        elif row[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return False

Drag options to blanks, or click blank then click option'

Arow[mid]

Btarget

Cleft

Dright

Attempts:

3 left

💡 Hint

Common Mistakes

Comparing the middle element to itself instead of the target.

Using wrong variables in the condition.

The binary search compares the middle element row[mid] with the target. So the condition should check if row[mid] == target.

4fill in blank

hard

Fill both blanks to complete the function that searches the target in the 2D matrix.

DSA Python

def search_matrix(matrix, target):
    for i in range(len(matrix)):
        if matrix[i][-1] >= target:
            return [1](matrix[i], target)
    return False

def binary_search(row, target):
    left, right = 0, len(row) - 1
    while left <= right:
        mid = (left + right) // 2
        if row[mid] == target:
            return True
        elif row[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return False

print(search_matrix(matrix, 16))

Drag options to blanks, or click blank then click option'

Abinary_search

Bsearch_matrix

Cmatrix

Drow

Attempts:

3 left

💡 Hint

Common Mistakes

Calling the wrong function.

Passing the whole matrix instead of a single row.

The search_matrix function calls binary_search on the found row to check if the target exists. The row is matrix[i], passed as row.

5fill in blank

hard

Fill all three blanks to create a dictionary comprehension that maps each row index to True if the target is found in that row using binary search.

DSA Python

def binary_search(row, target):
    left, right = 0, len(row) - 1
    while left <= right:
        mid = (left + right) // 2
        if row[mid] == target:
            return True
        elif row[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return False

matrix = [[1, 3, 5], [7, 9, 11], [13, 15, 17]]
target = 9
result = [1]: [2](matrix[i], target) for i in range(len(matrix)) if matrix[i][-1] >= target
print(result)

Drag options to blanks, or click blank then click option'

Ai

Bbinary_search

CTrue

DFalse

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong keys or values in the comprehension.

Not calling binary_search correctly.

The dictionary comprehension uses the row index i as key, calls binary_search on matrix[i] with the target, and stores True if found.

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