Scale Engineer

Search a 2D Matrix II

Med
#0228Time: O(m*n) where m is number of rows and n is number of columnsSpace: O(1) as we only use constant extra space9 companies
Algorithms
Binary SearchDivide and Conquer
Data structures
ArrayMatrix
Companies
ByteDanceOraclePayPaltcs

Prompt

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
  • -109 <= matrix[i][j] <= 109
  • All the integers in each row are sorted in ascending order.
  • All the integers in each column are sorted in ascending order.
  • -109 <= target <= 109

Approaches

3 approaches with complexity analysis and trade-offs.

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

Algorithm

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

Walkthrough

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

Time

O(m*n) where m is number of rows and n is number of columns

Space

O(1) as we only use constant extra space

Trade-offs

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

Solutions

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 walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem