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