Wednesday, August 19, 2015

Leetcode: Search a 2D Matrix II

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
  • Integers in each row are sorted in ascending from left to right.
  • Integers in each column are sorted in ascending from top to bottom.
For example,
Consider the following 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]
]
Given target = 5, return true.
Given target = 20, return false.
Understand the problem:
The sorted matrix indicates a binary search. However, since the matrix is not entirely sorted, we cannot treat the 2D array as 1D. 

The brute-force solution would be search each row, so the complexity would be O(m * log n). We could apply binary search and divide and conquer. 

A divide-and-conquer solution:
We could divide the entire matrix by a 4 x 4 panel, i.e, upper-left, upper-right, lower-left and lower-right. 
 -- If the target is equal to the middle, i.e, 9 in the example above, then we are done. 
 -- If the target is less than 9, then the lower-right part would be eliminated. 
 -- If the target is greater than 9, the upper-left part would be eliminated. 

Let's take a look at a wrong implementation first. 

A wrong implementation: 
public class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }
        
        int m = matrix.length;
        int n = matrix[0].length;
        
        return helper(matrix, 0, m - 1, 0, n - 1, target);
    }
    
    private boolean helper(int[][] matrix, int rowStart, int rowEnd, int colStart, int colEnd, int target) {
        if (rowStart > rowEnd || colStart > colEnd) {
            return false;
        }
        
        int rowMid = rowStart + (rowEnd - rowStart) / 2;
        int colMid = colStart + (colEnd - colStart) / 2;
        
        if (matrix[rowMid][colMid] == target) {
            return true;
        }
        
        if (matrix[rowMid][colMid] > target) {
            return helper(matrix, rowStart, rowMid - 1, colStart, colMid - 1, target) ||
                helper(matrix, rowMid, rowEnd, colStart, colMid - 1, target) ||
                helper(matrix, rowStart, rowMid - 1, colMid, colEnd, target);
        } else {
            return helper(matrix, rowMid, rowEnd, colMid, colEnd, target) ||
                helper(matrix, rowMid, rowEnd, colStart, colMid - 1, target) ||
                helper(matrix, rowStart, rowMid - 1, colMid, colEnd, target);
        }
    }
}

Runtime Error Message:Line 30: java.lang.StackOverflowError
Last executed input:[[-5]], -2

Analysis:
Why the solution is wrong? Take a look at the last If-else-branch (target > middle). If the target is greater than the middle number, we did not eliminate the middle as well its left and upper numbers. It would result in dead-loop as shown in the test case. 

Therefore, we should change the search boundary for the case when the target is greater than the middle. 

Correct Solution (Java):
public class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }
        
        int m = matrix.length;
        int n = matrix[0].length;
        
        return helper(matrix, 0, m - 1, 0, n - 1, target);
    }
    
    private boolean helper(int[][] matrix, int rowStart, int rowEnd, int colStart, int colEnd, int target) {
        if (rowStart > rowEnd || colStart > colEnd) {
            return false;
        }
        
        int rowMid = rowStart + (rowEnd - rowStart) / 2;
        int colMid = colStart + (colEnd - colStart) / 2;
        
        if (matrix[rowMid][colMid] == target) {
            return true;
        }
        
        if (matrix[rowMid][colMid] > target) {
            return helper(matrix, rowStart, rowMid - 1, colStart, colMid - 1, target) ||
                helper(matrix, rowMid, rowEnd, colStart, colMid - 1, target) ||
                helper(matrix, rowStart, rowMid - 1, colMid, colEnd, target);
        } else {
            return helper(matrix, rowMid + 1, rowEnd, colMid + 1, colEnd, target) ||
                helper(matrix, rowMid + 1, rowEnd, colStart, colMid, target) ||
                helper(matrix, rowStart, rowMid, colMid + 1, colEnd, target);
        }
    }
}

Analysis:
What's the time complexity for this solution? Since we only eliminate one fourth of the entire matrix in each recursion, the time complexity should be greater than O(log (m + n))

A O(m + n) solution:
The idea is starting from the lower-leftmost element, and compare with the target. 
 -- If equals to the target, stop.
 -- If target is less than the element, move up
 -- If the target is greater than the element, move right. 

public class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }
        
        int m = matrix.length;
        int n = matrix[0].length;
        
        int row = m - 1;
        int col = 0;
        
        while (row >= 0 && col < n) {
            if (target == matrix[row][col]) {
                return true;
            } else if (target < matrix[row][col]) {
                row--;
            } else {
                col++;
            }
        }
        return false;
    }
}

No comments:

Post a Comment