Off-by-one on range boundaries
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Move from brute-force thinking to an efficient approach using array strategy.
Write an efficient algorithm that searches for a value target in an m x n integer matrix matrix. This matrix has the following properties:
Example 1:
Input: 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]], target = 5 Output: true
Example 2:
Input: 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]], target = 20 Output: false
Constraints:
m == matrix.lengthn == matrix[i].length1 <= n, m <= 300-109 <= matrix[i][j] <= 109-109 <= target <= 109Problem summary: Write an efficient algorithm that searches for a value target in an m x n integer matrix matrix. This matrix has the following properties: Integers in each row are sorted in ascending from left to right. Integers in each column are sorted in ascending from top to bottom.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Array · Binary Search
[[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]] 5
[[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]] 20
search-a-2d-matrix)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #240: Search a 2D Matrix II
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
for (var row : matrix) {
int j = Arrays.binarySearch(row, target);
if (j >= 0) {
return true;
}
}
return false;
}
}
// Accepted solution for LeetCode #240: Search a 2D Matrix II
func searchMatrix(matrix [][]int, target int) bool {
for _, row := range matrix {
j := sort.SearchInts(row, target)
if j < len(matrix[0]) && row[j] == target {
return true
}
}
return false
}
# Accepted solution for LeetCode #240: Search a 2D Matrix II
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
for row in matrix:
j = bisect_left(row, target)
if j < len(matrix[0]) and row[j] == target:
return True
return False
// Accepted solution for LeetCode #240: Search a 2D Matrix II
use std::cmp::Ordering;
impl Solution {
pub fn search_matrix(matrix: Vec<Vec<i32>>, target: i32) -> bool {
let m = matrix.len();
let n = matrix[0].len();
let mut i = 0;
let mut j = n;
while i < m && j > 0 {
match target.cmp(&matrix[i][j - 1]) {
Ordering::Less => {
j -= 1;
}
Ordering::Greater => {
i += 1;
}
Ordering::Equal => {
return true;
}
}
}
false
}
}
// Accepted solution for LeetCode #240: Search a 2D Matrix II
function searchMatrix(matrix: number[][], target: number): boolean {
const n = matrix[0].length;
for (const row of matrix) {
const j = _.sortedIndex(row, target);
if (j < n && row[j] === target) {
return true;
}
}
return false;
}
Use this to step through a reusable interview workflow for this problem.
Check every element from left to right until we find the target or exhaust the array. Each comparison is O(1), and we may visit all n elements, giving O(n). No extra space needed.
Each comparison eliminates half the remaining search space. After k comparisons, the space is n/2ᵏ. We stop when the space is 1, so k = log₂ n. No extra memory needed — just two pointers (lo, hi).
Review these before coding to avoid predictable interview regressions.
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Wrong move: Setting `lo = mid` or `hi = mid` can stall and create an infinite loop.
Usually fails on: Two-element ranges never converge.
Fix: Use `lo = mid + 1` or `hi = mid - 1` where appropriate.