Coding

Search in 2D matrix - II

Asked at

Adobe

Amazon

MakeMyTrip

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

Given a 2D array matrix where each row is sorted in ascending order from left to right and each column is sorted in ascending order from top to bottom, write an efficient algorithm to search for a specific integer target in the matrix.

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 Explanation: The target 5 exists in the matrix in the index (1,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 = 20 Output: False Explanation: The target 20 does not exist in the matrix.

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 = 1

n == matrix.length
m == 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

cpp

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

java

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

python

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

javascript

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

csharp

public class Solution {
    public bool SearchMatrix(List<List<int>> matrix, int target) {
        
    }
}

func searchMatrix(matrix [][]int, target int) bool {
    //your code goes here
}

Stuck? Show a way to structure it+

01Start at the top-right or bottom-left corner.
02Move left when the current value is too large and down when it is too small.
03Stop on equality or after leaving the matrix.
04Use a corner with opposite monotonic directions, such as top right.

Reference answer

Start at the top-right cell. If it equals the target, return true. If it is larger than the target, every value below it in the same column is at least as large, but moving down cannot help; move left to a smaller value. If it is smaller than the target, every value to its left in the same row is no larger, so move down. Each comparison eliminates an entire row or column from consideration. The pointer moves at most rows - 1 times down and columns - 1 times left, giving O(rows + columns) time and O(1) space. Starting at the top-left does not provide the same one-direction elimination because both right and down are larger. A per-row binary search works in O(rows log columns) but does not use the column ordering as fully.

Then expect these follow-ups

What changes if each row is sorted but columns are not?
Tests: requirements
Why is top-right a useful starting corner?
Tests: elimination proof

Free to read · better with Enzo

Practice this out loud with Enzo

Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.

Continue with Enzo Sign up free

Next question