LeetCode 240 - Search a 2D Matrix II

LeetCode Problem 240

Difficulty: 🟡 Medium
Topics: Array, Binary Search, Divide and Conquer, Matrix

Solution

Problem Understanding

The problem asks us to determine whether a given integer target exists inside an m x n matrix. Unlike a completely unsorted matrix, this matrix has two important ordering guarantees:

1. Each row is sorted in ascending order from left to right.
2. Each column is sorted in ascending order from top to bottom.

We are given the matrix and a target integer, and we must return true if the target appears anywhere in the matrix, otherwise false.

In other words, this is not simply a search through arbitrary numbers. The matrix has a special structure that allows us to eliminate large portions of the search space without checking every element.

For example, consider this 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]
]

If we are searching for 5, the answer is true because the number exists in the matrix. If we search for 20, the answer is false because it does not appear.

The constraints tell us important information about scale:

• 1 <= m, n <= 300, meaning the matrix can contain up to 90,000 elements.
• Matrix values range from -10^9 to 10^9, so we cannot rely on small-value optimizations such as counting arrays.
• Rows and columns are guaranteed to be sorted.

Since the matrix can be fairly large, a naive solution that checks every element may still pass in practice, but the problem explicitly asks for an efficient algorithm. This strongly suggests we should exploit the sorted structure.

Several edge cases are important to recognize upfront. The matrix may contain only a single element, so the implementation must correctly handle 1 x 1 inputs. The target may be smaller than the smallest element or larger than the largest element, which should quickly result in false. The matrix can also contain negative numbers, so the algorithm must not assume positivity. Finally, because rows and columns are sorted independently, the matrix is not globally sorted if flattened into a single array, meaning binary search over the entire matrix is not valid.

Approaches

Brute Force Approach

The simplest solution is to examine every element in the matrix one by one and compare it with the target.

We iterate through each row, then iterate through every number in that row. If we ever encounter the target, we immediately return true. If we finish scanning the entire matrix without finding it, we return false.

This approach is guaranteed to be correct because it checks every possible position where the target could exist. If the target appears anywhere, we will eventually encounter it.

However, this solution ignores the sorted structure of the matrix. In the worst case, we inspect all m * n elements. With up to 90,000 entries, this is unnecessarily expensive when better methods exist.

Optimal Approach, Top Right Corner Search

The key insight comes from using the matrix ordering intelligently.

Suppose we start at the top right corner of the matrix.

At any position (row, col):

• Everything below is greater than or equal to the current value because columns are sorted.
• Everything to the left is smaller than or equal to the current value because rows are sorted.

This gives us a powerful elimination strategy:

• If the current value equals the target, we are done.
• If the current value is larger than the target, we move left, because everything below would only be larger.
• If the current value is smaller than the target, we move down, because everything to the left would only be smaller.

Each move eliminates either an entire row or an entire column from consideration.

Since we move at most m times downward and n times leftward, the total work becomes O(m + n).

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(m × n)	O(1)	Check every element individually
Optimal	O(m + n)	O(1)	Start from top right and eliminate rows or columns

Algorithm Walkthrough

Optimal Algorithm

1. Initialize a pointer at the top right corner of the matrix.

We choose this position because it gives us directional information. From the top right corner, moving left decreases values and moving down increases values.

Start here
       ↓
[1, 4, 7,11,15]
[2, 5, 8,12,19]
[3, 6, 9,16,22]

2. Compare the current value with the target.

If the current value equals the target, return true immediately because we found the desired element. 3. If the current value is larger than the target, move left.

Since the column is sorted top to bottom, every number below is even larger. Therefore, the entire current column can be discarded. 4. If the current value is smaller than the target, move down.

Since the row is sorted left to right, every number to the left is smaller. Therefore, the entire current row can be discarded. 5. Continue until either:

• We find the target and return true
• We move outside matrix bounds and return false

Going out of bounds means every viable position has been eliminated.

Why it works

The algorithm works because of a maintained invariant: at every step, the remaining search area still contains every possible location where the target could exist.

When we move left after seeing a value larger than the target, we safely eliminate an entire column because all values below are even larger. Similarly, when we move down after seeing a value smaller than the target, we safely eliminate an entire row because all values to the left are smaller. Since each decision removes impossible candidates without discarding valid possibilities, the algorithm is guaranteed to find the target if it exists.

Python Solution

from typing import List

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        rows = len(matrix)
        cols = len(matrix[0])

        row = 0
        col = cols - 1

        while row < rows and col >= 0:
            current_value = matrix[row][col]

            if current_value == target:
                return True

            if current_value > target:
                col -= 1
            else:
                row += 1

        return False

The implementation begins by determining the number of rows and columns. Since the problem guarantees at least one row and one column, we can safely access matrix[0].

We initialize our search position at the top right corner by setting row = 0 and col = cols - 1.

The while loop continues as long as we remain inside matrix boundaries. At each iteration, we examine matrix[row][col].

If the current value equals the target, we immediately return True.

If the current value is too large, we decrement col to move left because everything below is even larger and therefore impossible.

If the current value is too small, we increment row to move downward because everything to the left is smaller and therefore impossible.

If the loop exits, it means all valid search positions have been exhausted, so we return False.

Go Solution

func searchMatrix(matrix [][]int, target int) bool {
	rows := len(matrix)
	cols := len(matrix[0])

	row := 0
	col := cols - 1

	for row < rows && col >= 0 {
		currentValue := matrix[row][col]

		if currentValue == target {
			return true
		}

		if currentValue > target {
			col--
		} else {
			row++
		}
	}

	return false
}

The Go implementation follows exactly the same logic as the Python version. We compute the matrix dimensions, start from the top right corner, and repeatedly eliminate rows or columns based on comparison results.

One small Go-specific detail is the use of slices ([][]int) rather than lists. Since the problem guarantees a non-empty matrix, accessing matrix[0] is safe and requires no extra guard condition. Integer overflow is not a concern because comparisons are performed directly and matrix values fit comfortably within Go's integer range.

Worked Examples

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

We start at the top right corner.

Step	Position (row, col)	Value	Comparison	Action
1	(0, 4)	15	15 > 5	Move left
2	(0, 3)	11	11 > 5	Move left
3	(0, 2)	7	7 > 5	Move left
4	(0, 1)	4	4 < 5	Move down
5	(1, 1)	5	5 == 5	Return true

The target is found at position (1,1).

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

Step	Position (row, col)	Value	Comparison	Action
1	(0, 4)	15	15 < 20	Move down
2	(1, 4)	19	19 < 20	Move down
3	(2, 4)	22	22 > 20	Move left
4	(2, 3)	16	16 < 20	Move down
5	(3, 3)	17	17 < 20	Move down
6	(4, 3)	26	26 > 20	Move left
7	(4, 2)	23	23 > 20	Move left
8	(4, 1)	21	21 > 20	Move left
9	(4, 0)	18	18 < 20	Move down, out of bounds

Since we leave the matrix without finding the target, the result is false.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(m + n)	Each step moves either one row down or one column left
Space	O(1)	Only a few variables are used

The time complexity is O(m + n) because we never revisit cells. Each movement reduces either the row range or the column range. Since there are at most m downward moves and n leftward moves, the total number of operations is linear in the matrix dimensions.

The space complexity is O(1) because the algorithm uses only a few integer variables and does not allocate any additional data structures.

Test Cases

solution = Solution()

# Example cases
assert solution.searchMatrix(
    [[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
) is True  # target exists

assert solution.searchMatrix(
    [[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
) is False  # target missing

# Single element matrix
assert solution.searchMatrix([[5]], 5) is True  # exact match
assert solution.searchMatrix([[5]], 3) is False  # no match

# Single row matrix
assert solution.searchMatrix([[1, 3, 5, 7]], 5) is True  # present
assert solution.searchMatrix([[1, 3, 5, 7]], 6) is False  # absent

# Single column matrix
assert solution.searchMatrix([[1], [3], [5], [7]], 3) is True  # present
assert solution.searchMatrix([[1], [3], [5], [7]], 4) is False  # absent

# Target smaller than minimum
assert solution.searchMatrix([[5, 6], [7, 8]], 1) is False

# Target larger than maximum
assert solution.searchMatrix([[5, 6], [7, 8]], 100) is False

# Negative values
assert solution.searchMatrix(
    [[-10, -5, 0],
     [-8, -3, 2],
     [-6, -1, 4]], -3
) is True  # negative target exists

# Duplicate values
assert solution.searchMatrix(
    [[1, 2, 2],
     [2, 3, 4],
     [3, 4, 5]], 2
) is True  # duplicates handled

# Large target absent near boundary
assert solution.searchMatrix(
    [[1, 10, 20],
     [2, 15, 25],
     [5, 18, 30]], 29
) is False

Test	Why
Example 1	Verifies successful search
Example 2	Verifies unsuccessful search
Single element match	Smallest valid input
Single element miss	Boundary case
Single row	Tests horizontal traversal
Single column	Tests vertical traversal
Smaller than minimum	Immediate elimination scenario
Larger than maximum	Boundary rejection
Negative numbers	Confirms sign handling
Duplicate values	Ensures duplicates do not break logic
Missing near boundary	Tests elimination accuracy

Edge Cases

Single Element Matrix

A 1 x 1 matrix is the smallest possible valid input. This case can expose indexing mistakes or boundary-condition bugs. For example, implementations with incorrect loop conditions may accidentally move outside bounds immediately. Our implementation handles this naturally because the search begins at the only element and performs exactly one comparison.

Target Outside Matrix Range

If the target is smaller than the smallest element or larger than the largest element, a naive algorithm may still scan much of the matrix unnecessarily. For example:

[
 [5, 6],
 [7, 8]
]

Searching for 1 or 100 should quickly fail. The top-right search naturally eliminates rows or columns until it exits bounds, correctly returning false.

Single Row or Single Column

Matrices with only one row or one column behave differently because movement becomes one-dimensional. Bugs often occur when algorithms assume both dimensions are larger than one. In a single-row matrix, the algorithm repeatedly moves left. In a single-column matrix, it repeatedly moves downward. Since our loop condition explicitly checks bounds, both cases are handled correctly without special-case logic.

Negative Numbers and Large Values

Because values can range from -10^9 to 10^9, implementations must avoid assumptions about positivity or small ranges. Our solution relies only on comparisons, not arithmetic tricks or indexing based on value magnitude, so it works correctly regardless of number size or sign.