Given a m x n matrix, which 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.
Given a target value, return if the matrix contains this value.
For Example:
Given 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 = 9, return true.
Given target = 16, return true.
Given target = 25, return false.
Solution:
brutal force solution is loop through the 2D array, compare each single element with the target, the time complexity is O(mn), the space complexity is O(1).
The above solution didn't use the sorted property. The sorted property can be used by binary search, with some ugly code, we can hope to achieve nlogn performance.
We can also use recursive approach. One way is to start from top left, search row and column, find the boundary points, then shrink the searching range to row+1, rowboundary and col+1, colboundary.
There is an elegant and faster solution using the sorted property.
Let's start at the bottom left corner, and move up and right, if we found the target before moving out of the boundary, we return true, otherwise false. This solution is not hard to come into mind, however, the hard part is: after naturally trying the start point at top-left corner without success, instead of giving up and trying different approaches such as recursive and binary search, we should realize the approach is the best, the start point caused all the difficulties.
import java.util.*;
class Solution {
public static void main(String[] args) {
int[][] matrix = new int[][] {
{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}
};
int row = matrix.length;
int col = matrix[0].length;
System.out.println(contains(matrix, 9));
System.out.println(contains(matrix, 16));
System.out.println(contains(matrix, 20));
System.out.println(contains(matrix, 25));
System.out.println(contains(matrix, 0));
System.out.println(contains(matrix, 18));
System.out.println(contains(matrix, 15));
System.out.println(contains(matrix, 1));
}
private static boolean contains(int[][] matrix, int target) {
int rowMax = matrix.length - 1;
int colMax = matrix[0].length - 1;
int i = rowMax;
int j = 0;
while(j <= colMax && i >= 0) {
if(matrix[i][j] == target) return true;
if(matrix[i][j] > target) --i;
else ++j;
}
return false;
}
}
class Solution {
public static void main(String[] args) {
int[][] matrix = new int[][] {
{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}
};
int row = matrix.length;
int col = matrix[0].length;
System.out.println(contains(matrix, 9));
System.out.println(contains(matrix, 16));
System.out.println(contains(matrix, 20));
System.out.println(contains(matrix, 25));
System.out.println(contains(matrix, 0));
System.out.println(contains(matrix, 18));
System.out.println(contains(matrix, 15));
System.out.println(contains(matrix, 1));
}
private static boolean contains(int[][] matrix, int target) {
int rowMax = matrix.length - 1;
int colMax = matrix[0].length - 1;
int i = rowMax;
int j = 0;
while(j <= colMax && i >= 0) {
if(matrix[i][j] == target) return true;
if(matrix[i][j] > target) --i;
else ++j;
}
return false;
}
}
The time complexity is O(m+n) the space complexity is O(1).
