Facebook | Phone | Search in a sorted matrix with duplicates
Anonymous User
1785
MetaPhone ScreeningInterview

Hi,
I just had an interview with Facebook.

Question:
https://leetcode.com/problems/search-a-2d-matrix-ii/ expect that i had to return the coordinate.

My solution 
var searchMatrix = function(matrix, target) {
    if (!matrix || matrix.length === 0)
        return false;
    
    let row = 0;
    let col = matrix[0].length - 1;
    
    while (
        (row >= 0 && row < matrix.length) &&
        (col >= 0 && col < matrix[0].length)) {    
            
        if (matrix[row][col] === target)
            return [row, col];
			
        if (target < matrix[row][col])
            col--;
        else
            row++;
    }
    
    return null;
};

Follow-up:
Return all coordinates since the 2d array can contain duplicates.

My first intuition was to re-use my code but do DFS from the first coordinate found.

Sample code 
var searchMatrix = function(matrix, target) {
    if (!matrix || matrix.length === 0)
        return false;
    
    let row = 0;
    let col = matrix[0].length - 1;
    let results = [];
	
    while (
        (row >= 0 && row < matrix.length) &&
        (col >= 0 && col < matrix[0].length)) {    
            
        if (matrix[row][col] === target) {
            dfs(matrix, row, col, results); // This does dfs (left or down only)
			return results;
		}
			
        if (target < matrix[row][col])
            col--;
        else
            row++;
    }
    
    return results;
};

However the interview told me he was looking for a faster solution. I couldn't come up with a solution so he told me that he wanted to do vertical and horizontal binary search to find the additional coordinates.
Maybe i'm missing something but i can't understand how his solution would be faster than using DFS.

Comments (6)