Search a 2D Matrix II

MEDIUM

Description

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.length
n == matrix[i].length
1 <= n, m <= 300
-10⁹ <= matrix[i][j] <= 10⁹
All the integers in each row are sorted in ascending order.
All the integers in each column are sorted in ascending order.
-10⁹ <= target <= 10⁹

Approaches

Checkout 3 different approaches to solve Search a 2D Matrix II. Click on different approaches to view the approach and algorithm in detail.

Brute Force Approach

The simplest approach is to search every element in the matrix one by one until we find the target element.

Algorithm

Iterate through each row of the matrix (i from 0 to m-1)
For each row, iterate through each column (j from 0 to n-1)
If current element equals target, return true
If target not found after complete iteration, return false

In this approach, we iterate through each element in the matrix using nested loops. For each element, we compare it with the target value. If we find a match, we return true. If we complete the search without finding the target, we return false.

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        int n = matrix[0].length;
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == target) {
                    return true;
                }
            }
        }
        return false;
    }
}

Complexity Analysis

Time Complexity: O(m*n) where m is number of rows and n is number of columnsSpace Complexity: O(1) as we only use constant extra space

Pros and Cons

Pros:

Simple to implement
No extra space required
Works for any matrix (sorted or unsorted)

Cons:

Does not utilize the sorted property of the matrix
Very inefficient for large matrices
Checks every element even when unnecessary

Code Solutions

Checking out 5 solutions in different languages for Search a 2D Matrix II. Click on different languages to view the code.

public class Solution { public bool SearchMatrix ( int [][] matrix , int target ) { int m = matrix . Length , n = matrix [ 0 ]. Length ; int i = m - 1 , j = 0 ; while ( i >= 0 && j < n ) { if ( matrix [ i ][ j ] == target ) { return true ; } if ( matrix [ i ][ j ] > target ) { -- i ; } else { ++ j ; } } return false ; } }

Video Solution

Watch the video walkthrough for Search a 2D Matrix II

Algorithms:

Binary SearchDivide and Conquer

Data Structures:

ArrayMatrix

Companies:

ByteDance |Oracle |PayPal |tcs |