Search a 2D Matrix

▶

Steps

setup

Initialize matrix dimensions and search boundaries

Calculate the number of rows (m) and columns (n) in the matrix. Initialize left pointer to 0 and right pointer to the last index of the flattened array (m*n - 1).

💡 Setting up the search boundaries is essential to treat the 2D matrix as a 1D sorted array for binary search.

Line:

m, n = len(matrix), len(matrix[0])
left, right = 0, m * n - 1

💡 The entire matrix is now represented as a linear array from index 0 to 11 (3 rows * 4 columns - 1).

compare

Calculate mid index for first comparison

Calculate mid as the integer division of (left + right) by 2, which is (0 + 11) // 2 = 5.

💡 Midpoint calculation splits the search space roughly in half to efficiently narrow down the target location.

Line:

mid = (left + right) // 2

💡 Mid index 5 corresponds to the middle element in the flattened array.

compare

Map mid index to 2D matrix coordinates

Convert mid index 5 to 2D indices: row = 5 // 4 = 1, col = 5 % 4 = 1. The element at matrix[1][1] is 11.

💡 Mapping mid to 2D indices lets us access the actual matrix element for comparison.

Line:

row, col = divmod(mid, n)

💡 Mid index 5 corresponds to matrix element 11 at row 1, column 1.

compare

Compare mid element with target

Compare matrix[1][1] = 11 with target 3. Since 11 > 3, the target must be in the left half.

💡 Comparison determines which half of the search space to eliminate.

Line:

if matrix[row][col] == target:
    return True
elif matrix[row][col] < target:
    left = mid + 1
else:
    right = mid - 1

💡 Eliminate the right half by moving right pointer to mid - 1 = 4.

shrink

Update right pointer to narrow search space

Set right pointer to mid - 1 = 4, reducing the search space to indices 0 through 4.

💡 Updating pointers focuses the search on the remaining possible locations of the target.

Line:

right = mid - 1

💡 Search space is now smaller, excluding elements greater than target.

compare

Calculate new mid index for next comparison

Calculate mid as (left + right) // 2 = (0 + 4) // 2 = 2.

💡 Recalculate mid to continue binary search in the updated search space.

Line:

mid = (left + right) // 2

💡 Mid index 2 is the new candidate for comparison.

compare

Map new mid index to 2D matrix coordinates

Convert mid index 2 to 2D indices: row = 2 // 4 = 0, col = 2 % 4 = 2. The element at matrix[0][2] is 5.

💡 Mapping mid to 2D indices allows access to the matrix element for comparison.

Line:

row, col = divmod(mid, n)

💡 Mid index 2 corresponds to matrix element 5 at row 0, column 2.

compare

Compare mid element with target again

Compare matrix[0][2] = 5 with target 3. Since 5 > 3, eliminate right half again.

💡 Comparison guides the next pointer update to narrow the search space.

Line:

if matrix[row][col] == target:
    return True
elif matrix[row][col] < target:
    left = mid + 1
else:
    right = mid - 1

💡 Right pointer moves to 1, further shrinking the search space.

shrink

Update right pointer to mid - 1

Set right pointer to mid - 1 = 1, narrowing search space to indices 0 through 1.

💡 Pointer update excludes elements greater than target.

Line:

right = mid - 1

💡 Search space now only includes first two elements.

compare

Calculate mid index for final comparison

Calculate mid as (left + right) // 2 = (0 + 1) // 2 = 0.

💡 Mid recalculation continues the binary search in the reduced space.

Line:

mid = (left + right) // 2

💡 Mid index 0 is the next candidate for comparison.

compare

Map mid index 0 to 2D matrix coordinates

Convert mid index 0 to 2D indices: row = 0 // 4 = 0, col = 0 % 4 = 0. The element at matrix[0][0] is 1.

💡 Mapping mid to 2D indices allows element access for comparison.

Line:

row, col = divmod(mid, n)

💡 Mid index 0 corresponds to matrix element 1 at row 0, column 0.

compare

Compare mid element 1 with target 3

Since 1 < 3, move left pointer to mid + 1 = 1 to search the right half.

💡 Comparison guides pointer updates to focus on the half that may contain the target.

Line:

elif matrix[row][col] < target:
    left = mid + 1

💡 Left pointer moves to 1, narrowing search space to index 1.

compare

Calculate mid index for final element

Calculate mid as (left + right) // 2 = (1 + 1) // 2 = 1.

💡 Mid calculation focuses on the last remaining element in the search space.

Line:

mid = (left + right) // 2

💡 Mid index 1 is the last candidate for comparison.

compare

Map mid index 1 to 2D matrix coordinates

Convert mid index 1 to 2D indices: row = 1 // 4 = 0, col = 1 % 4 = 1. The element at matrix[0][1] is 3.

💡 Mapping mid to 2D indices accesses the matrix element for final comparison.

Line:

row, col = divmod(mid, n)

💡 Mid index 1 corresponds to matrix element 3 at row 0, column 1.

compare

Compare mid element with target and find match

Since matrix[0][1] = 3 equals the target 3, the search is successful and returns true.

💡 Finding the target ends the search immediately.

Line:

if matrix[row][col] == target:
    return True

💡 The target is found at index 1 in the flattened array, corresponding to matrix[0][1].

def searchMatrix(matrix, target):
    if not matrix or not matrix[0]:
        return False
    m, n = len(matrix), len(matrix[0])  # STEP 1
    left, right = 0, m * n - 1  # STEP 1
    while left <= right:  # STEP 3
        mid = (left + right) // 2  # STEP 2,6,10,13
        row, col = divmod(mid, n)  # STEP 3,7,11,14
        if matrix[row][col] == target:  # STEP 4,8,15
            return True
        elif matrix[row][col] < target:  # STEP 12
            left = mid + 1
        else:  # STEP 4,8
            right = mid - 1
    return False

📊

Search a 2D Matrix - Watch the Algorithm Execute, Step by Step

Watching each comparison and pointer update helps you understand how binary search efficiently locates the target in a 2D matrix without scanning every element.

Target: 3

lo

1

0

3

1

5

2

7

3

10

4

11

5

16

6

20

7

23

8

30

9

34

10

hi

60

11

Next: lo=0 hi=11

Target: 3

lo

1

0

3

1

5

2

7

3

10

4

mid

11

5

16

6

20

7

23

8

30

9

34

10

hi

60

11

mid[5]=11

Next: lo=0 hi=11

Target: 3

lo

1

0

3

1

5

2

7

3

10

4

mid

11

5

16

6

20

7

23

8

30

9

34

10

hi

60

11

mid[5]=11 - matrix[1][1] = 11 compared to target 3

Next: lo=0 hi=11

Target: 3

lo

1

0

3

1

5

2

7

3

10

4

mid

11

5

16

6

20

7

23

8

30

9

34

10

hi

60

11

mid[5]=11 - 11 > 3, eliminate right half

Next: lo=0 hi=4

Target: 3

lo

1

0

3

1

5

2

7

3

hi

10

4

mid

11

5

16

6

20

7

23

8

30

9

34

10

60

11

mid[5]=11 - right updated to 4

Next: lo=0 hi=4

Target: 3

lo

1

0

3

1

mid

5

2

7

3

hi

10

4

11

5

16

6

20

7

23

8

30

9

34

10

60

11

mid[2]=5

Next: lo=0 hi=4

Target: 3

lo

1

0

3

1

mid

5

2

7

3

hi

10

4

11

5

16

6

20

7

23

8

30

9

34

10

60

11

mid[2]=5 - matrix[0][2] = 5 compared to target 3

Next: lo=0 hi=4

Target: 3

lo

1

0

3

1

mid

5

2

7

3

hi

10

4

11

5

16

6

20

7

23

8

30

9

34

10

60

11

mid[2]=5 - 5 > 3, eliminate right half

Next: lo=0 hi=1

Target: 3

lo

1

0

hi

3

1

mid

5

2

7

3

10

4

11

5

16

6

20

7

23

8

30

9

34

10

60

11

mid[2]=5 - right updated to 1

Next: lo=0 hi=1

Target: 3

lo/mid

1

0

hi

3

1

5

2

7

3

10

4

11

5

16

6

20

7

23

8

30

9

34

10

60

11

mid[0]=1

Next: lo=0 hi=1

Target: 3

lo/mid

1

0

hi

3

1

5

2

7

3

10

4

11

5

16

6

20

7

23

8

30

9

34

10

60

11

mid[0]=1 - matrix[0][0] = 1 compared to target 3

Next: lo=0 hi=1

Target: 3

lo/mid

1

0

hi

3

1

5

2

7

3

10

4

11

5

16

6

20

7

23

8

30

9

34

10

60

11

mid[0]=1 - 1 < 3, eliminate left half

Next: lo=1 hi=1

Target: 3

1

0

lo/mid/hi

3

1

5

2

7

3

10

4

11

5

16

6

20

7

23

8

30

9

34

10

60

11

mid[1]=3

Next: lo=1 hi=1

Target: 3

1

0

lo/mid/hi

3

1

5

2

7

3

10

4

11

5

16

6

20

7

23

8

30

9

34

10

60

11

mid[1]=3 - matrix[0][1] = 3 compared to target 3

Next: lo=1 hi=1

Target: 3

1

0

lo/mid/hi

3

1

5

2

7

3

10

4

11

5

16

6

20

7

23

8

30

9

34

10

60

11

mid[1]=3 - 3 == 3, target found

Next: lo=1 hi=1

Key Takeaways

✓ Binary search can be applied to a 2D matrix by treating it as a 1D sorted array.

This insight is hard to see from code alone because the mapping between 2D and 1D indices is implicit.

✓ Each comparison eliminates half of the search space, drastically reducing the number of elements to check.

Visualizing pointer movements clarifies how the algorithm efficiently narrows down the search.

✓ Mapping mid index back to 2D coordinates is crucial for accessing matrix elements during the search.

Seeing this mapping step-by-step helps understand how the algorithm bridges 1D indexing with 2D data.

Practice

1. You need to ship packages within a given number of days. Each package has a weight, and you must ship packages in order without splitting any package. You want to find the minimum ship capacity to ship all packages within the deadline. Which algorithmic approach guarantees finding the optimal ship capacity efficiently?

easy

A. Greedy approach that assigns packages to days until capacity is reached, then moves to next day without binary search

B. Dynamic programming to find the minimum capacity by exploring all subsets of packages and days

C. Sorting packages and using a two-pointer technique to assign packages to days

D. Binary search on the answer space (capacity) combined with a feasibility check to verify if shipping within days is possible

Solution

1. Step 1: Understand the problem constraints

   The problem requires finding a minimum capacity that allows shipping all packages in order within a fixed number of days.

2. Step 2: Recognize the pattern

   Binary searching the capacity (answer space) and checking feasibility is the optimal approach because capacity ranges between max package weight and sum of all weights, and feasibility can be checked in linear time.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Binary search on answer space is classic for optimization with feasibility checks [OK]

Hint: Binary search on capacity range solves this optimally [OK]

Common Mistakes:

• Thinking greedy alone finds minimal capacity
• Confusing DP with subset sums
• Using two pointers without sorting relevance

2. The following code attempts to find the kth positive missing number from a sorted array arr. Which line contains a subtle bug that causes incorrect results for some inputs?

def findKthPositive(arr, k):
    n = len(arr)
    total_missing = arr[-1] - n
    if k > total_missing:
        return arr[-1] + (k - total_missing)
    left, right = 0, n - 1
    while left <= right:
        mid = (left + right) // 2
        missing = arr[mid] - mid  # Bug here
        if missing < k:
            left = mid + 1
        else:
            right = mid - 1
    return arr[right] + (k - (arr[right] - (right + 1)))

medium

A. Line returning arr[right] + (k - (arr[right] - (right + 1)))

B. Line calculating total_missing = arr[-1] - n

C. Line updating left = mid + 1

D. Line calculating missing = arr[mid] - mid

Solution

1. Step 1: Identify the missing count formula

   The correct missing count at index mid is arr[mid] - (mid + 1), since indices are zero-based but numbers start at 1.

2. Step 2: Analyze the bug impact

   Using arr[mid] - mid undercounts missing numbers by 1, causing incorrect binary search decisions and wrong final result.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Correct missing count formula is arr[mid] - (mid + 1) [OK]

Hint: Missing count must subtract (mid + 1), not mid [OK]

Common Mistakes:

• Off-by-one in missing count calculation
• Incorrect binary search boundary updates
• Ignoring missing numbers before first element

3. The following code attempts to find the kth smallest element in a sorted matrix using a min-heap. Identify the line containing the subtle bug that can cause incorrect results when duplicates exist or when counting is off.

medium

A. Line where count is incremented after the kth check (count += 1)

B. Line where initial elements are pushed into the heap (heapq.heappush in for loop)

C. Line where the kth element is checked (if count == k: return val)

D. Line where next element in the row is pushed (heapq.heappush inside while loop)

Solution

1. Step 1: Understand counting logic

   Count should increment before checking if count == k to correctly identify the kth popped element.

2. Step 2: Identify off-by-one bug

   Currently, count is incremented after the check, so the function returns the (k-1)th element instead of kth.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Increment count before kth check fixes off-by-one error [OK]

Hint: Check order of count increment and kth check [OK]

Common Mistakes:

• Off-by-one in counting popped elements
• Returning before incrementing count
• Misplaced heap push causing missing elements

4. Suppose the array is no longer sorted and may contain duplicates, and you still need to count occurrences of a target efficiently. Which approach is best suited to handle this scenario?

hard

A. Use binary search on the unsorted array to find boundaries

B. Sort the array first, then use binary search to count occurrences

C. Use a hash map to count occurrences in a single pass

D. Use a greedy approach to skip duplicates and count

Solution

1. Step 1: Recognize unsorted array limitation

   Binary search requires sorted data; it cannot be applied directly here.

2. Step 2: Evaluate alternatives

   Sorting first adds O(n log n) overhead; hash map counting is O(n) and direct.

3. Step 3: Choose hash map approach

   Hash map counts occurrences in one pass with O(n) time and O(n) space, optimal for unsorted arrays.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Hash map counting works regardless of order [OK]

Hint: Unsorted array -> hash map counting [OK]

Common Mistakes:

• Trying binary search on unsorted data
• Sorting then binary searching is slower
• Greedy skipping duplicates misses counts

5. Suppose the problem is modified so that the array is sorted but the single element can appear multiple times (not necessarily once), and all other elements appear exactly twice. Which modification to the binary search approach correctly finds the single element?

hard

A. Modify binary search to compare mid with neighbors and adjust search space based on counts of duplicates around mid

B. Switch to linear scan because binary search parity logic breaks when single element repeats

C. Use the same parity-based binary search since duplicates still appear in pairs

D. Use a hash map to count occurrences since binary search can't handle multiple single elements

Solution

1. Step 1: Understand problem change

   The single element may appear multiple times, breaking the strict pair pattern.

2. Step 2: Analyze binary search adaptation

   Parity-based halving fails; instead, compare mid with neighbors and count duplicates to decide which half to search.

3. Step 3: Confirm other options

   Linear scan is inefficient; hash map uses extra space and is unnecessary if modified binary search works.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Counting duplicates around mid guides correct binary search [OK]

Hint: Modify binary search to handle variable duplicate counts [OK]

Common Mistakes:

• Assuming parity logic still works
• Switching to linear scan prematurely
• Using extra space unnecessarily