Search⌘ K
AI Features
Home
Courses
Coderust: Hacking the Coding Interview

Search in a Matrix

Understand how to search for a key in a 2D matrix where each row and column is sorted. Discover an efficient O(m+n) time algorithm starting from the top right corner, improving beyond naive scanning or binary search per row. Learn the logic to traverse the matrix while minimizing time and space complexity. This lesson equips you with a practical approach to handle matrix search problems commonly encountered in coding interviews.

We'll cover the following...

Statement

Given a 2D array where all elements in any individual row or column are sorted. Find the position of a given key in such a matrix. If the key is not present in the matrix, return (−1,−1)(-1, -1).

Example

The following example elaborates on this problem:

g matrix 0 1 2 3 4 0 2 4 7 13 15 1 3 5 11 18 22 2 6 8 16 21 28 3 9 11 20 25 31 text Since the key value exists in the matrix, the output  should be the key's position in the matrix, i.e. (2,2). k key: 16

Sample input

( [[ 2,  4,  7, 13, 15],
   [ 3,  5, 11, 18, 22],
   [ 6,  8, 16, 21, 28],
   [ 9, 11, 20, 25, 31]], 16 )

Expected output

(2, 2)

Try it yourself

Note: The matrix used in the evaluation is the same as the one mentioned above.

#include <iostream>
#include <vector>
using namespace std;
pair<int, int> SearchInMatrix(vector<vector<int>> matrix, int value) {
	// TODO: Write - Your - Code
	return pair<int, int>(-1, -1);
}

Solution

A straightforward solution is to scan the whole 2D array for the key in O(m×n ...