Search a 2D Matrix II solution and explanation
Google
9 more videos on this problem
Search a 2D Matrix II | Live Coding with Explanation | Leetcode - 240Algorithms Made Easy · 7:06 · 15K views
Leetcode - Search a 2D Matrix II (Python)Timothy H Chang · 4:47 · 8K views
LeetCode 240. Search a 2D Matrix II Explanation and Solutionhappygirlzt · 6:02 · 2K views
Daily Leetcode #845: Jul 24, 2022 - 240. Search a 2D Matrix IIProgramming Live with Larry · 9:39 · 611 views
Search a 2D Matrix II | Leetcode 240 | Binary Search | C++Tech Courses · 7:34 · 374 views
Search a 2D Matrix II | Binary Search 🔥 | LeetCode Solution 240Gantavya Malviya · 9:50 · 251 views
Leetcode 240: Search in 2D Matrix II | Java SolutionMaybe Something New · 8:05 · 197 views
240. Search a 2D Matrix II | Leetcode MediumJOY of LIFE · 14:02 · 166 views
Leetcode 240: Search a 2D Matrix II - Swift Programming Language SolutionEverythingSwift · 8:27 · 143 views
BS-25. Search in a 2D Matrix - II | Binary Search on 2Dtake U forward · 15:29 · 205K views
The problem
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.
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- All the integers in each row are sorted in ascending order.
- All the integers in each column are sorted in ascending order.
-109 <= target <= 109
Approach overview
Problem Overview: You are given an m x n matrix where each row is sorted left to right and each column is sorted top to bottom. The task is to determine whether a target value exists in the matrix without scanning every element.
Approach 1: Start from Top-Right Corner (O(m + n) time, O(1) space)
This approach exploits the sorted structure of both rows and columns. Start at the top-right element. From this position, each comparison eliminates either a full row or a full column. If the current value is greater than the target, move left because all values below are even larger. If the value is smaller than the target, move down since everything to the left is smaller. Each step removes one row or column from consideration, so you perform at most m + n moves.
The key insight: the top-right corner acts like a pivot where one direction strictly decreases and the other strictly increases. This allows deterministic movement similar to a two-pointer scan in a sorted grid. The algorithm uses only index movement and comparisons, so the extra memory remains constant. This technique frequently appears in problems involving sorted matrices and grid monotonicity, making it a useful pattern for array and matrix search problems.
Approach 2: Binary Search in Rows (O(m log n) time, O(1) space)
Another option is to treat each row as an independent sorted array and apply binary search. Iterate through every row and check whether the target can exist in that row by comparing it with the row's first and last elements. If the target falls within that range, run binary search on that row to locate it.
This works because each row is individually sorted, which fits the classic binary search pattern. However, you still need to iterate through up to m rows, and each binary search costs O(log n). The result is O(m log n) time. While slower than the optimal solution, this approach is straightforward to implement and easy to reason about during interviews.
Recommended for interviews: Interviewers usually expect the top-right traversal. It shows you recognize the monotonic ordering across both dimensions and can eliminate rows or columns in constant time per step. The row-wise binary search approach demonstrates understanding of sorted arrays, but the O(m + n) strategy highlights stronger algorithmic insight and familiarity with matrix search patterns often discussed alongside divide and conquer style reasoning.
Approach 1: Approach 1: Start from Top-Right Corner
This approach begins searching from the top-right corner of the matrix. If the current element is equal to the target, return true. If the current element is greater than the target, move left. If the current element is less than the target, move down. This method effectively narrows down the search space, taking advantage of the sorted property of the matrix.
def searchMatrix(matrix, target):
row, col = 0, len(matrix[0]) - 1
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 Falsepublic class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int row = 0, col = matrix[0].length - 1;
while (row < matrix.length && col >= 0) {
if (matrix[row][col] == target) {
return true;
} else if (matrix[row][col] > target) {
col--;
} else {
row++;
}
}
return false;
}
}#include <vector>
class Solution {
public:
bool searchMatrix(std::vector<std::vector<int>>& matrix, int target) {
int row = 0, col = matrix[0].size() - 1;
while (row < matrix.size() && col >= 0) {
if (matrix[row][col] == target) {
return true;
} else if (matrix[row][col] > target) {
col--;
} else {
row++;
}
}
return false;
}
};function searchMatrix(matrix, target) {
let row = 0;
let col = matrix[0].length - 1;
while (row < matrix.length && col >= 0) {
if (matrix[row][col] === target) {
return true;
} else if (matrix[row][col] > target) {
col--;
} else {
row++;
}
}
return false;
}#include <stdbool.h>
bool searchMatrix(int** matrix, int matrixSize, int* matrixColSize, int target) {
int row = 0, col = matrixColSize[0] - 1;
while (row < matrixSize && col >= 0) {
if (matrix[row][col] == target) {
return true;
} else if (matrix[row][col] > target) {
col--;
} else {
row++;
}
}
return false;
}public class Solution {
public bool SearchMatrix(int[][] matrix, int target) {
int row = 0;
int col = matrix[0].Length - 1;
while (row < matrix.Length && col >= 0) {
if (matrix[row][col] == target) {
return true;
} else if (matrix[row][col] > target) {
col--;
} else {
row++;
}
}
return false;
}
}The Python implementation makes use of similar logic as other language solutions, taking advantage of Python's simplicity and dynamic typing to efficiently track indices and compare values.
Time Complexity: O(m + n).
Space Complexity: O(1).
Approach 2: Approach 2: Binary Search in Rows
This approach uses binary search on each row of the matrix. Since each row is sorted, binary search can efficiently determine if the target exists within the row. If found in any row, the function returns true.
def binary_search(row, target):
left, right = 0, len(row) - 1
while left <= right:
mid = left + (right - left) // 2
if row[mid] == target:
return True
elif row[mid] < target:
left = mid + 1
else:
right = mid - 1
return False
def searchMatrix(matrix, target):
for row in matrix:
if binary_search(row, target):
return True
return Falsepublic class Solution {
private boolean binarySearch(int[] row, int target) {
int left = 0, right = row.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (row[mid] == target) return true;
else if (row[mid] < target) left = mid + 1;
else right = mid - 1;
}
return false;
}
public boolean searchMatrix(int[][] matrix, int target) {
for (int[] row : matrix) {
if (binarySearch(row, target)) return true;
}
return false;
}
}#include <vector>
class Solution {
public:
bool binarySearch(const std::vector<int>& array, int target) {
int left = 0, right = array.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (array[mid] == target) return true;
else if (array[mid] < target) left = mid + 1;
else right = mid - 1;
}
return false;
}
bool searchMatrix(std::vector<std::vector<int>>& matrix, int target) {
for (const auto& row : matrix) {
if (binarySearch(row, target)) return true;
}
return false;
}
};function binarySearch(array, target) {
let left = 0, right = array.length - 1;
while (left <= right) {
let mid = Math.floor(left + (right - left) / 2);
if (array[mid] === target) return true;
else if (array[mid] < target) left = mid + 1;
else right = mid - 1;
}
return false;
}
function searchMatrix(matrix, target) {
for (let row of matrix) {
if (binarySearch(row, target)) return true;
}
return false;
}#include <stdbool.h>
bool binarySearch(int* array, int size, int target) {
int left = 0, right = size - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (array[mid] == target) return true;
else if (array[mid] < target) left = mid + 1;
else right = mid - 1;
}
return false;
}
bool searchMatrix(int** matrix, int matrixSize, int* matrixColSize, int target) {
for (int i = 0; i < matrixSize; i++) {
if (binarySearch(matrix[i], matrixColSize[i], target)) return true;
}
return false;
}public class Solution {
private bool BinarySearch(int[] array, int target) {
int left = 0, right = array.Length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (array[mid] == target) return true;
else if (array[mid] < target) left = mid + 1;
else right = mid - 1;
}
return false;
}
public bool SearchMatrix(int[][] matrix, int target) {
foreach (var row in matrix) {
if (BinarySearch(row, target)) return true;
}
return false;
}
}The Python function defines an internal helper `binary_search` which operates on each row. It iteratively applies binary search to rows, leveraging the sorted property to quickly declutter impossible sections.
Time Complexity: O(m * log(n)).
Space Complexity: O(1).
Approach 3: Binary Search
Since all elements in each row are sorted in ascending order, for each row, we can use binary search to find the first element greater than or equal to target, and then check if that element is equal to target. If it is equal to target, it means the target value is found, and we return true. If it is not equal to target, it means all elements in this row are less than target, and we should continue searching the next row.
If all rows have been searched and the target value is not found, it means the target value does not exist, and we return false.
The time complexity is O(m times log n), where m and n are the number of rows and columns of the matrix, respectively. The space complexity is O(1).
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;
}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
}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
}
}Approach 4: Search from Bottom-Left or Top-Right
We start the search from the bottom-left or top-right corner and move towards the top-right or bottom-left direction. Compare the current element matrix[i][j] with target:
- If
matrix[i][j] = target, it means the target value is found, and we returntrue. - If
matrix[i][j] > target, it means all elements in this column from the current position upwards are greater thantarget, so we move theipointer upwards, i.e.,i \leftarrow i - 1. - If
matrix[i][j] < target, it means all elements in this row from the current position to the right are less thantarget, so we move thejpointer to the right, i.e.,j \leftarrow j + 1.
If the search ends and the target is not found, return false.
The time complexity is O(m + n), where m and n are the number of rows and columns of the matrix, respectively. The space complexity is O(1).
function searchMatrix(matrix: number[][], target: number): boolean {
const [m, n] = [matrix.length, matrix[0].length];
let [i, j] = [m - 1, 0];
while (i >= 0 && j < n) {
if (matrix[i][j] === target) {
return true;
}
if (matrix[i][j] > target) {
--i;
} else {
++j;
}
}
return false;
}func searchMatrix(matrix [][]int, target int) bool {
m, n := len(matrix), len(matrix[0])
i, j := m-1, 0
for i >= 0 && j < n {
if matrix[i][j] == target {
return true
}
if matrix[i][j] > target {
i--
} else {
j++
}
}
return false
}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 = m - 1;
let mut j = 0;
while i >= 0 && j < n {
if matrix[i][j] == target {
return true;
}
if matrix[i][j] > target {
if i == 0 {
break;
}
i -= 1;
} else {
j += 1;
}
}
false
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Start from Top-Right Corner | Time Complexity: O(m + n). |
| Approach 2: Binary Search in Rows | Time Complexity: O(m * log(n)). |
| Binary Search | – |
| Search from Bottom-Left or Top-Right | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Top-Right Corner Traversal | O(m + n) | O(1) | Best general solution when rows and columns are both sorted |
| Binary Search in Each Row | O(m log n) | O(1) | Useful when treating rows as independent sorted arrays |
Frequently asked questions
Is Search a 2D Matrix II easy or hard?
Search a 2D Matrix II is generally classified as a medium difficulty problem. The challenge is recognizing that the sorted rows and columns allow elimination of entire rows or columns, leading to the O(m + n) traversal strategy.
How to solve Search a 2D Matrix II in O(m+n)?
Start from the top-right element of the matrix. Compare it with the target. If it is larger, move one column left; if smaller, move one row down. Because rows increase left to right and columns increase top to bottom, each move removes an entire row or column from the search space.
Search a 2D Matrix II Python or Java solution?
In Python or Java, the most common solution initializes two indices at the top-right corner of the matrix. A loop moves left or down based on comparisons with the target until the element is found or the indices move outside the matrix bounds.
What is the best approach for Search a 2D Matrix II?
The optimal approach starts from the top-right corner of the matrix and eliminates one row or one column after each comparison. If the current value is larger than the target, move left; if smaller, move down. This strategy runs in O(m + n) time and O(1) space, making it the most efficient solution for this problem.
What data structure is used in Search a 2D Matrix II?
The core data structure is a 2D matrix (grid) implemented as a 2D array. The algorithm relies on the sorted property of rows and columns and uses pointer-style traversal or binary search to efficiently locate the target.
What is the time complexity of Search a 2D Matrix II?
The optimal solution runs in O(m + n) time where m is the number of rows and n is the number of columns. Each step discards either a row or a column, so you perform at most m + n comparisons. Space complexity is O(1) because the algorithm only uses a few index variables.
Is Search a 2D Matrix II asked at Google, Amazon, or Meta?
Search a 2D Matrix II is a common interview problem at large tech companies including Google, Amazon, and Meta. It tests understanding of matrix traversal, monotonic ordering, and the ability to reduce search space efficiently without scanning the entire grid.