seanpgallivan

Posted on

# Solution: Search a 2D Matrix II

This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums.

#### Description:

(Jump to: Solution Idea || Code: JavaScript | Python | Java | C++)

Write an efficient algorithm that searches for a `target` value in an `m x n` integer `matrix`. The `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.

#### 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
Output: true
Visual:
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
Visual:

#### Constraints:

• `m == matrix.length`
• `n == matrix[i].length`
• `1 <= n, m <= 300`
• `-10^9 <= matix[i][j] <= 10^9`
• All the integers in each row are sorted in ascending order.
• All the integers in each column are sorted in ascending order.
• `-10^9 <= target <= 10^9`

#### Idea:

(Jump to: Problem Description || Code: JavaScript | Python | Java | C++)

The naive approach here would be to check every cell at a time complexity of O(m * n). The obvious improvement on this would be to use a binary search on each row to shorten this to O(m * log n). But since the matrix (M) is sorted both by row and by column, we can actually think of each cell (M[i][j]) as being a midpoint in a longer "row", including all the cells to the left as well as below the current cell.

If we start from the top right corner of M and treat this like a modified binary search, we can eliminate an entire row or an entire column each time we check a cell:

We'll then just need to adjust our i or j value to move to the top right corner "midpoint" of the remaining matrix each time to narrow in on our target (T):

This will drop the time complexity to O(m + n).

(Note: This works just as well when starting from the bottom left corner.)

#### Implementation:

For all except Java we can use the bitwise NOT operator (~) to check for boundary condition of j because it will return a falsy value (0) only when j is -1.

(Note: Some people are achieving "faster" results by exploiting a design flaw in the testing suite. It appears that the test includes one or more loops of the same matrix input and people have had the idea to clear the matrix before returning the answer, which will make the rest of said loop easier to process, as the mutated matrix will be used in subsequent iterations of the test.)

#### Javascript Code:

``````var searchMatrix = function(M, T) {
let y = M.length, i = 0, j = M[0].length - 1
while (i < y && ~j) {
let cell = M[i][j]
if (cell === T) return true
else if (cell > T) j--
else i++
}
return false
};

``````

#### Python Code:

``````class Solution:
def searchMatrix(self, M: List[List[int]], T: int) -> bool:
y, i, j = len(M), 0, len(M[0]) - 1
while i < y and ~j:
cell = M[i][j]
if cell == T: return True
elif cell > T: j -= 1
else: i += 1
return False
``````

#### Java Code:

``````class Solution {
public boolean searchMatrix(int[][] M, int T) {
int y = M.length, i = 0, j = M[0].length - 1;
while (i < y && j >= 0) {
int cell = M[i][j];
if (cell == T) return true;
else if (cell > T) j--;
else i++;
}
return false;
}
}
``````

#### C++ Code:

``````class Solution {
public:
bool searchMatrix(vector<vector<int>>& M, int T) {
int y = M.size(), i = 0, j = M[0].size() - 1;
while (i < y && ~j) {
int cell = M[i][j];
if (cell == T) return true;
else if (cell > T) j--;
else i++;
}
return false;
}
};
``````