LeetCode Hot 100 P240 Search a 2D Matrix II

---

Timeline

Timeline

2026-03-13

init

Matrix, Divide and Conquer

---

Problem:

P240 Search a 2D Matrix II

https://leetcode.cn/problems/search-a-2d-matrix-ii/description/?envType=study-plan-v2&envId=top-100-liked

At first, I thought like this:

#include <vector>
using std::vector;

class Solution {
    private:
        int binary_search_column(vector<vector<int> > &matrix, int target, int column)
        {
                // Binary search by column
                // 1 <= n, m <= 300
                int m = matrix.size();
                int left = 0, right = m - 1, mid;

                while (left < right) {
                        mid = (left + right) / 2;
                        if (matrix[mid][column] > target) {
                                right = mid - 1;
                        } else if (matrix[mid][column] < target) {
                                left = mid + 1;
                        } else {
                                return mid;
                        }
                }
                // if not found it should return greatest value that < target
                if (matrix[left][column] <= target)
                        return left;
                else
                        return left == 0 ? 0 : left - 1;
        }
        int binary_search_row(vector<vector<int> > &matrix, int target, int row)
        {
                // Binary search by row
                int n = matrix[0].size();
                int left = 0, right = n - 1, mid;

                while (left < right) {
                        mid = (left + right) / 2;
                        if (matrix[row][mid] > target) {
                                right = mid - 1;
                        } else if (matrix[row][mid] < target) {
                                left = mid + 1;
                        } else {
                                return mid;
                        }
                }
                if (matrix[row][left] <= target)
                        return left;
                else
                        return left == 0 ? 0 : left - 1;
        }

    public:
        bool searchMatrix(vector<vector<int> > &matrix, int target)
        {
                // 1 <= n, m <= 300
                int row, column;
                // First row
                column = binary_search_row(matrix, target, 0);
                if (matrix[0][column] == target)
                        return true;
                row = binary_search_column(matrix, target, column);
                if (matrix[row][column] == target)
                        return true;

                // First column
                row = binary_search_column(matrix, target, 0);
                if (matrix[row][0] == target)
                        return true;

                column = binary_search_row(matrix, target, row);
                if (matrix[row][column] == target)
                        return true;

                return false;
        }
};

int main()
{
        Solution S;
        // vector<vector<int> > 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 } };

        // vector<vector<int> > matrix = { { 1, 2, 3, 4, 5 },
        //                                 { 6, 7, 8, 9, 10 },
        //                                 { 11, 12, 13, 14, 15 },
        //                                 { 16, 17, 18, 19, 20 },
        //                                 { 21, 22, 23, 24, 25 } };

        vector<vector<int> > matrix = { { 1, 3, 5, 7, 9 },
                                        { 2, 4, 6, 8, 10 },
                                        { 11, 13, 15, 17, 19 },
                                        { 12, 14, 16, 18, 20 },
                                        { 21, 22, 23, 24, 25 } };

        // int target = 5;
        // int target = 19;

        int target = 13;
        S.searchMatrix(matrix, target);
}

But obviously, the target cannot be found in the third test case.

In fact, we should start searching from the top-right corner:

#include <vector>
using std::vector;

class Solution {
    public:
        bool searchMatrix(vector<vector<int> > &matrix, int target)
        {
                // 1 <= n, m <= 300
                int m = matrix.size(), n = matrix[0].size();
                int row = 0, column = n - 1;

                // Start searching from the top-right corner
                while (row >= 0 && row < m && column >= 0 && column < n) {
                        if (matrix[row][column] < target) {
                                row++;
                        } else if (matrix[row][column] > target) {
                                column--;
                        } else {
                                return true;
                        }
                }

                return false;
        }
};

int main()
{
        Solution S;
        // vector<vector<int> > 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 } };

        // vector<vector<int> > matrix = { { 1, 2, 3, 4, 5 },
        //                                 { 6, 7, 8, 9, 10 },
        //                                 { 11, 12, 13, 14, 15 },
        //                                 { 16, 17, 18, 19, 20 },
        //                                 { 21, 22, 23, 24, 25 } };

        vector<vector<int> > matrix = { { 1, 3, 5, 7, 9 },
                                        { 2, 4, 6, 8, 10 },
                                        { 11, 13, 15, 17, 19 },
                                        { 12, 14, 16, 18, 20 },
                                        { 21, 22, 23, 24, 25 } };

        // int target = 5;
        // int target = 19;

        int target = 13;
        S.searchMatrix(matrix, target);
}