LeetCode 240: Search a 2D Matrix II

Explanation

To solve this problem efficiently, we can start from the top right corner of the matrix. If the target is smaller than the current element, we move left since all elements in the current row are greater. If the target is larger, we move down since all elements in the current column are smaller. By following this approach, we can eliminate rows and columns at each step and eventually find the target or determine it doesn't exist.

• Algorithm:

  1. Start from the top right corner.
  2. If the target is smaller, move left.
  3. If the target is larger, move down.
  4. Repeat until the target is found or the current position is out of bounds.

• Time Complexity: O(m + n) - where m is the number of rows and n is the number of columns.

• Space Complexity: O(1) - constant space is used.

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