Last updated on March 2nd, 2025 at 05:24 pm

Here, we see a Search a 2D Matrix LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Array, Binary Search

Level of Question

Medium

Search a 2D Matrix LeetCode Solution

1. Problem Statement

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 from left to right.
• The first integer of each row is greater than the last integer of the previous row.

Example 1:

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true

Example 2:

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Output: false

2. Coding Pattern Used in Solution

The coding pattern used in the provided code is “Modified Binary Search”. This pattern is applied when the search space is sorted or can be treated as sorted, and the problem can be solved by dividing the search space into halves iteratively or recursively.

3. Code Implementation in Different Languages

3.1 Search a 2D Matrix C++

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
    if(matrix.empty() || matrix[0].empty())
    {
        return false;
    }
    int m = matrix.size(), n = matrix[0].size();
    int start = 0, end = m*n - 1;
    while(start <= end)
    {
        int mid = start + (end - start)/2;
        int e = matrix[mid/n][mid%n];
        if(target < e)
        {
            end = mid - 1;
        }
        else if(target > e)
        {
            start = mid + 1;
        }
        else
        {
            return true;
        }
    }
    return false;        
    }
};

3.2 Search a 2D Matrix Java

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

3.3 Search a 2D Matrix JavaScript

var searchMatrix = function(matrix, target) {
  if (!matrix.length || !matrix[0].length) return false;

  let row = 0;
  let col = matrix[0].length - 1;

  while (col >= 0 && row <= matrix.length - 1) {
    if (matrix[row][col] === target) return true;
    else if (matrix[row][col] > target) col--;
    else if (matrix[row][col] < target) row++;
  }

  return false;    
};

3.4 Search a 2D Matrix Python

class Solution(object):
    def searchMatrix(self, matrix, target):
        if not matrix:
            return False
        row = len(matrix)       # Number of Rows of the matrix...
        col = len(matrix[0])    # Number of Columns of the matrix...
        beg = 0
        end = row*col
        while beg < end:
            mid = beg + (end - beg) // 2
            idx = matrix[mid / col][mid % col];
            if idx == target:
                return True
            if idx < target:
                beg = mid + 1
            else:
                end = mid
        return False 

4. Time and Space Complexity

	Time Complexity	Space Complexity
C++	O(log(m * n))	O(1)
Java	O(m + n)	O(1)
JavaScript	O(m + n)	O(1)
Python	O(log(m * n))	O(1)

• C++ and Python use a Modified Binary Search approach, treating the matrix as a flattened 1D array.
• Java and JavaScript use a Greedy Search approach, starting from the top-right corner and moving left or down based on comparisons.
• The time complexity for binary search is logarithmic, while the greedy search approach has linear complexity in terms of rows and columns.
• All implementations have constant space complexity as no additional data structures are used.