Coderust: Hacking the Coding Interview/

...

/

Search in a Matrix

Search in a Matrix

Find the position of a given key in a 2D matrix in which all rows and columns are sorted.

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 ...