Coding

Search in a 2D matrix

Asked at

Visa

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

Given a 2-D array mat where the elements of each row are sorted in non-decreasing order, and the first element of a row is greater than the last element of the previous row (if it exists), and an integer target, determine if the target exists in the given mat or not.

Input: mat = [ [1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12] ], target = 8 Output: True Explanation: The target = 8 exists in the 'mat' at index (1, 3).

Input: mat = [ [1, 2, 4], [6, 7, 8], [9, 10, 34] ], target = 78 Output: False Explanation: The target = 78 does not exist in the 'mat'. Therefore in the output, we see 'false'.

Input: mat = [ [1, 2, 4], [6, 7, 8], [9, 10, 34] ], target = 7

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

cpp

class Solution{
public:
    bool searchMatrix(vector<vector<int>> &mat, int target){
        
    }
};

java

class Solution {
    public boolean searchMatrix(int[][] mat, int target) {

    }
}

python

class Solution:
    def searchMatrix(self, mat, target):

javascript

class Solution {
    searchMatrix(mat, target) {
   
    }
}

csharp

class Solution
{
    public bool SearchMatrix(List<List<int>> mat, int target)
    {
        // Write your code here
    }
}

func searchMatrix(mat [][]int, target int) bool {
	
}

Stuck? Show a way to structure it+

01Treat the matrix as a sorted array of length m*n.
02Binary-search indices from 0 to m*n-1.
03Map an index to row and column with division and modulo.
04Compare and narrow normally.
05Handle empty dimensions first.

Reference answer

When every row is sorted and the first element of a row exceeds the last element of the previous row, flatten conceptually without copying. Binary search integers lo = 0 through hi = m*n - 1. For mid, look up matrix[mid / n][mid % n]; integer division selects the row and modulo selects the column. Compare that value to the target and move the appropriate bound exactly as for a normal sorted array. Check an empty matrix or empty first row before accessing n. This approach uses the full global ordering, is simpler than first selecting a row, and runs in O(log(m*n)) time with O(1) extra space. Mention that it does not apply to the version where only row and column ordering is guaranteed.

Then expect these follow-ups

How do you solve the row-and-column sorted version?
Tests: staircase search
How do duplicates affect the result?
Tests: binary search

Hiring now

Visa has 638 open roles right now

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Software Engineer Intern
GB - London, United Kingdom
Sr. Software Engineer (3+ yrs, DevOps, Cloud, Coding, Infra)
IN - Bengaluru, India
Sr Software Engineer (3-5 yrs of exp - Full stack development, Java, React, Gen AI)
IN - Bengaluru, India

Or practice this question first

Next question