Search a 2D Matrix

📋

Problem

Imagine you have a large spreadsheet sorted row-wise and column-wise, and you want to quickly find if a certain value exists without scanning every cell.

Given an m x n matrix where each row is sorted in ascending order and the first integer of each row is greater than the last integer of the previous row, write a function that returns true if a given target value exists in the matrix, and false otherwise.

m == matrix.lengthn == matrix[i].length1 ≤ m, n ≤ 10^5 (total elements ≤ 10^5)-10^9 ≤ matrix[i][j], target ≤ 10^9

Edge cases: Empty matrix → falseMatrix with one element equal to target → trueMatrix with one element not equal to target → false

</>

IDE

def searchMatrix(matrix: list[list[int]], target: int) -> bool:public boolean searchMatrix(int[][] matrix, int target)bool searchMatrix(vector<vector<int>>& matrix, int target)function searchMatrix(matrix, target)

def searchMatrix(matrix, target):
    # Write your solution here
    pass

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        // Write your solution here
        return false;
    }
}

#include <vector>
using namespace std;

bool searchMatrix(vector<vector<int>>& matrix, int target) {
    // Write your solution here
    return false;
}

function searchMatrix(matrix, target) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: falseIncorrect index mapping from 1D mid to 2D matrix coordinates causing missed target.✅ Calculate row = mid // n and col = mid % n correctly before comparing matrix[row][col] to target.

Wrong: trueNo check for empty matrix or empty rows, causing false positives or errors.✅ Add guard clause: if not matrix or not matrix[0]: return false before binary search.

Wrong: trueFailing to return false when target is outside matrix value range (less than smallest or greater than largest).✅ Add early return if target < matrix[0][0] or target > matrix[m-1][n-1].

Wrong: falseBinary search loop conditions or mid updates incorrect causing infinite loops or missed matches in single-element or duplicate matrices.✅ Ensure low <= high loop condition and update low = mid + 1 or high = mid - 1 correctly.

Wrong: TLEUsing O(m*n) brute force or O(m*log n) binary search per row instead of O(log(m*n)) binary search over entire matrix.✅ Implement binary search treating matrix as a flattened sorted array with index mapping.

✓

Test Cases

Focus on handling empty and minimal input cases correctly.

Add boundary checks and consider duplicates and out-of-range targets.

Optimize your solution to logarithmic time complexity over the entire matrix.

t1_01basic

Input{"matrix":[[1,3,5,7],[10,11,16,20],[23,30,34,60]],"target":3}

Expectedtrue

⏱ Performance - must finish in 2000ms

3 is present in the first row, second column.

💡 Think about treating the 2D matrix as a sorted 1D array.

💡 Use binary search by mapping 1D indices to 2D coordinates.

💡 Calculate mid index, then row = mid // n, col = mid % n to check values.

Why it failed: Returned false or incorrect result for canonical example; likely binary search index mapping or mid calculation error. Fix by correctly mapping mid to matrix[row][col].

✓ Correctly found target using binary search with proper index mapping.

t1_02basic

Input{"matrix":[[1,2,3,4],[5,6,7,8],[9,10,11,12]],"target":10}

Expectedtrue

⏱ Performance - must finish in 2000ms

10 is present in the third row, second column.

💡 Remember the matrix is sorted row-wise and each row starts greater than previous row's end.

💡 Binary search over the entire matrix length m*n is efficient.

💡 Map mid index to row and column correctly to compare with target.

Why it failed: Failed to find target 10; likely off-by-one or incorrect mid calculation. Fix by ensuring mid calculation and index mapping are correct.

✓ Successfully located target 10 using binary search on flattened matrix.

t2_01edge

Input{"matrix":[],"target":1}

Expectedfalse

⏱ Performance - must finish in 2000ms

Empty matrix contains no elements, so target cannot be found.

💡 Check if the matrix or its first row is empty before searching.

💡 Return false immediately if matrix is empty to avoid errors.

💡 Add a guard clause for empty matrix to handle this edge case.

Why it failed: Code crashes or returns true on empty matrix; fix by adding check for empty matrix or empty rows before binary search.

✓ Correctly returns false for empty matrix input.

t2_02edge

Input{"matrix":[[5]],"target":5}

Expectedtrue

⏱ Performance - must finish in 2000ms

Single element matrix where element equals target.

💡 Handle single-element matrix as a base case.

💡 Binary search should still work but verify index calculations for single element.

💡 Ensure mid calculation and mapping works when m*n = 1.

Why it failed: Fails to find target in single-element matrix; fix by handling single-element case or verifying binary search boundaries.

✓ Successfully finds target in single-element matrix.

t2_03edge

Input{"matrix":[[5]],"target":3}

Expectedfalse

⏱ Performance - must finish in 2000ms

Single element matrix where element does not equal target.

💡 Check that binary search returns false when target is not present.

💡 Verify that low and high pointers are updated correctly for single element.

💡 Ensure no infinite loops or incorrect returns in this minimal case.

Why it failed: Incorrectly returns true or crashes on single-element matrix with no match; fix binary search loop conditions and return false if not found.

✓ Correctly returns false when target is absent in single-element matrix.

t3_01corner

Input{"matrix":[[1,3,5],[7,9,11],[13,15,17]],"target":0}

Expectedfalse

⏱ Performance - must finish in 2000ms

Target smaller than smallest element in matrix.

💡 Check if target is less than matrix[0][0] before searching.

💡 If target < smallest element, return false immediately.

💡 Add boundary checks to avoid unnecessary search.

Why it failed: Fails by searching unnecessarily or returning true; fix by adding early return if target < matrix[0][0]. This is the exact boundary test.

✓ Correctly returns false for target smaller than smallest element.

t3_02corner

Input{"matrix":[[1,3,5],[7,9,11],[13,15,17]],"target":18}

Expectedfalse

⏱ Performance - must finish in 2000ms

Target larger than largest element in matrix.

💡 Check if target is greater than matrix[m-1][n-1] before searching.

💡 If target > largest element, return false immediately.

💡 Add boundary checks to avoid unnecessary search.

Why it failed: Fails by searching unnecessarily or returning true; fix by adding early return if target > matrix[m-1][n-1]. This is the exact boundary test.

✓ Correctly returns false for target larger than largest element.

t3_03corner

Input{"matrix":[[1,1,1],[1,1,1],[1,1,1]],"target":1}

Expectedtrue

⏱ Performance - must finish in 2000ms

All elements identical and equal to target.

💡 Verify binary search handles duplicates correctly.

💡 Ensure mid calculation and comparisons do not cause infinite loops.

💡 Check that any occurrence of target returns true.

Why it failed: Fails to find target in matrix with all identical elements; fix by ensuring binary search mid updates and comparisons handle duplicates properly.

✓ Correctly finds target in matrix with all identical elements.

t4_01performance

Input{"_description":"n=100000 at constraint boundary - executor generates this"}

Expectednull

⏱ Performance - must finish in 2000ms

Matrix with 100000 elements; O(log(m*n)) binary search must complete within 2 seconds.

💡 Use binary search treating matrix as 1D sorted array for O(log(m*n)) complexity.

💡 Avoid nested loops or linear scans to prevent TLE.

💡 Map indices carefully to avoid overhead.

Why it failed: Solution times out due to O(m*n) or O(m*log n) approach; fix by implementing O(log(m*n)) binary search treating matrix as 1D array.

✓ Solution runs within time limit using O(log(m*n)) binary search.

Practice

1. Given the following code for finding a peak element, what is the final output when the input array is [1, 3, 2]?

def findPeakElement(nums):
    def binarySearch(low, high):
        if low == high:
            return low
        mid = (low + high) // 2
        if nums[mid] < nums[mid + 1]:
            return binarySearch(mid + 1, high)
        else:
            return binarySearch(low, mid)
    return binarySearch(0, len(nums) - 1)

print(findPeakElement([1, 3, 2]))

easy

A. None of the above

B. 0

C. 2

D. 1

Solution

1. Step 1: Trace first call binarySearch(0, 2)

   mid = (0+2)//2 = 1; nums[1]=3, nums[2]=2; since 3 > 2, recurse binarySearch(0,1)

2. Step 2: Trace second call binarySearch(0, 1)

   mid = (0+1)//2 = 0; nums[0]=1, nums[1]=3; since 1 < 3, recurse binarySearch(1,1)

3. Step 3: Trace third call binarySearch(1, 1)

   low == high, return 1

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Returned index 1 corresponds to peak element 3 [OK]

Hint: Check mid and mid+1 comparison carefully [OK]

Common Mistakes:

• Returning mid instead of low/high
• Off-by-one in mid calculation
• Confusing which half to recurse

2. Given the following code snippet, what is the final output when running with piles = [3, 6, 7, 11] and h = 8?

from math import ceil

def can_finish(piles, speed, h):
    hours = 0
    for pile in piles:
        hours += ceil(pile / speed)
        if hours > h:
            return false
    return true

def minEatingSpeed(piles, h):
    low, high = 1, max(piles)
    while low < high:
        mid = (low + high) // 2
        if can_finish(piles, mid, h):
            high = mid
        else:
            low = mid + 1
    return low

piles = [3,6,7,11]
h = 8
print(minEatingSpeed(piles, h))

easy

A. 3

B. 4

C. 5

D. 6

Solution

1. Step 1: Trace binary search iterations

   Initial low=1, high=11. mid=6: can_finish with speed=6 returns true (hours=3+1+2+2=8 ≤8), so high=6. Next mid=(1+6)//2=3: can_finish speed=3 returns false (hours=1+2+3+4=10 >8), so low=4. Next mid=(4+6)//2=5: can_finish speed=5 returns true (hours=1+2+2+3=8 ≤8), so high=5. Next mid=(4+5)//2=4: can_finish speed=4 returns true (hours=1+2+2+3=8 ≤8), so high=4. Now low=4, high=4, loop ends.

2. Step 2: Return final low value

   The minimum speed is 4.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Tracing confirms minimum speed is 4 [OK]

Hint: Check feasibility at mid speeds carefully [OK]

Common Mistakes:

• Off-by-one in binary search boundaries
• Miscounting hours with ceil division

3. Consider the following Python function maxDistanceOptimized that finds the largest minimum distance to place m balls in sorted positions. Given position = [1, 2, 4, 8] and m = 3, what is the final returned value?

easy

A. 2

B. 4

C. 3

D. 1

Solution

1. Step 1: Trace binary search boundaries

   Initial low=1, high=7 (8-1). Mid=4: can_place(4)? Positions: 1,2,4,8. Place first ball at 1, next at 8 (8-1=7≥4), count=2 < m=3 -> False.

2. Step 2: Adjust boundaries and find final result

   high=3, mid=2: can_place(2)? Place at 1, then 4 (4-1=3≥2), then 8 (8-4=4≥2), count=3 -> True. low=3, mid=3: can_place(3)? Place at 1, then 4 (3≥3), then 8 (4≥3), count=3 -> True. low=4, high=3 ends loop. Result=3.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Final max minimum distance is 3 [OK]

Hint: Check feasibility at mid distances carefully [OK]

Common Mistakes:

• Off-by-one in binary search boundaries
• Miscounting balls placed in can_place

4. What is the time complexity of the min-heap based approach to find the kth smallest element in an n x n sorted matrix, where k ≤ n²? Assume the heap operations take O(log n) time.

medium

A. O(k log n)

B. O(k log k)

C. O(n log k)

D. O(n^2 log n)

Solution

1. Step 1: Analyze heap size and operations

   The heap holds at most n elements (one from each row), so heap operations cost O(log n).

2. Step 2: Count total heap operations

   We pop and push at most k times, so total time is O(k log n).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Heap size bounded by n, operations proportional to k [OK]

Hint: Heap size limited to n, not k or n² [OK]

Common Mistakes:

• Assuming heap size grows to k or n²
• Confusing k and n in log factors
• Thinking complexity is O(n^2 log n)

5. Suppose Koko can eat bananas from multiple piles simultaneously each hour (i.e., she can split her eating speed across piles). How does this change the approach to find the minimum eating speed to finish within h hours?

hard

A. Feasibility check simplifies to total bananas ≤ speed * h, so minimum speed = ceil(total / h)

B. We must use dynamic programming to consider all pile combinations per hour

C. The original binary search with feasibility check still applies without changes

D. Binary search is invalid; a greedy approach is required instead

Solution

1. Step 1: Understand the new eating model

   Koko can split speed across piles simultaneously, so total bananas eaten per hour equals speed.

2. Step 2: Simplify feasibility condition

   To finish in h hours, total bananas ≤ speed * h, so minimum speed = ceil(total bananas / h).

3. Step 3: Conclude algorithm change

   No binary search needed; direct calculation suffices.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Splitting speed removes per-pile constraints, simplifying problem [OK]

Hint: Splitting speed means total bananas divided by hours [OK]

Common Mistakes:

• Applying original binary search blindly
• Overcomplicating with DP