Search a 2D Matrix II

Share

Given an m x n matrix where each row is sorted left to right and each column is sorted top to bottom, search for a target value.

Example 1
Input: matrix=[[1,4,7,11],[2,5,8,12],[3,6,9,16],[10,13,14,17],[18,21,23,26]], target=5 → Output: true
Example 2
Input: same matrix, target=20 → Output: false

Solution Approach

Start from top-right corner. If current > target: go left. If current < target: go down. If equal: return true.

  • r=0, c=n-1.
  • While r=0: if matrix[r][c]==target return true; if > target c--; else r++.
  • Return false.
Java
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int r=0, c=matrix[0].length-1;
        while (r<matrix.length && c>=0) {
            if (matrix[r][c]==target) return true;
            else if (matrix[r][c]>target) c--;
            else r++;
        }
        return false;
    }
}
  • Time Complexity: O(M+N)
  • Space Complexity: O(1)