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.

---

Leetcode Problem #240 (Medium): Search a 2D Matrix II

---

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:

(Jump to: Problem Description || Solution Idea)

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:

(Jump to: Problem Description || Solution Idea)

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:

(Jump to: Problem Description || Solution Idea)

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:

(Jump to: Problem Description || Solution Idea)

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;
    }
};

Comments

[Mbah Favour]

Wow...love your explanations