Scale Engineer

Search a 2D Matrix

Med
#0074Time: O(m * n)Space: O(1)20 companies
Algorithms
Binary Search
Data structures
ArrayMatrix
Companies
AccentureAdobeAmazonApple

Prompt

You are given an m x n integer matrix matrix with the following two properties:

  • Each row is sorted in non-decreasing order.
  • The first integer of each row is greater than the last integer of the previous row.

Given an integer target, return true if target is in matrix or false otherwise.

You must write a solution in O(log(m * n)) time complexity.

 

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

 

Constraints:

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 100
  • -104 <= matrix[i][j], target <= 104

Approaches

4 approaches with complexity analysis and trade-offs.

This is the most straightforward but least efficient approach. We can simply iterate through every cell of the m x n matrix and check if the element at that cell is equal to the target. This method does not take advantage of the matrix's special sorted structure.

Algorithm

  • Get the dimensions of the matrix, m (rows) and n (columns).
  • Iterate through each row i from 0 to m-1 using a for loop.
  • For each row i, iterate through each column j from 0 to n-1 using a nested for loop.
  • Inside the inner loop, check if the element matrix[i][j] is equal to the target.
  • If a match is found, return true immediately.
  • If the loops complete without finding the target, return false after the loops finish.

Walkthrough

The algorithm uses two nested loops to traverse the matrix. The outer loop iterates through the rows from index 0 to m-1, and the inner loop iterates through the columns from index 0 to n-1. In each iteration of the inner loop, we compare the current element matrix[row][col] with the target value. If they are equal, we have found the target and can return true. If we traverse the entire matrix and do not find the target, the loops will complete, and we return false.

class Solution {    public boolean searchMatrix(int[][] matrix, int target) {        int m = matrix.length;        if (m == 0) {            return false;        }        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)

Space

O(1)

Trade-offs

Pros

  • Very simple to understand and implement.

  • Works on any 2D matrix, regardless of whether it's sorted or not.

Cons

  • Highly inefficient as it does not leverage the sorted properties of the matrix.

  • Fails to meet the O(log(m * n)) time complexity requirement specified in the problem description.

Solutions

class Solution { public boolean searchMatrix ( int [][] matrix , int target ) { int m = matrix . length , n = matrix [ 0 ]. length ; int left = 0 , right = m * n - 1 ; while ( left < right ) { int mid = ( left + right ) >> 1 ; int x = mid / n , y = mid % n ; if ( matrix [ x ][ y ] >= target ) { right = mid ; } else { left = mid + 1 ; } } return matrix [ left / n ][ left % n ] == target ; } }

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