240. Search a 2D Matrix II

Description

The problem is to search for a target value in a 2D matrix where each row is sorted in ascending order, and each column is sorted in ascending order. The task is to determine whether the target value exists within the matrix.

Intuition

Given that the matrix is sorted both row-wise and column-wise, we can leverage this property to eliminate rows or columns efficiently, thereby narrowing down the search space. Starting from the top-right corner allows us to make decisions about whether to move left or down based on the comparison between the current element and the target.

Approach

1. Initialization: Start from the top-right corner of the matrix.
2. Search: - Compare the current element with the target. - If the current element is equal to the target, return True. - If the current element is greater than the target, move left to reduce the value. - If the current element is less than the target, move down to increase the value.
3. Termination: If we move out of the matrix bounds, return False as the target does not exist in the matrix.

Complexity

Time Complexity:

The time complexity is O(m + n), where m is the number of rows and n is the number of columns. In the worst case, we might traverse one row and one column completely.

Space Complexity:

The space complexity is O(1) since we are only using a constant amount of extra space.

Code

C++

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

Python

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        row = 0
        col = len(matrix[0]) - 1
        
        while row < len(matrix) and col >= 0:
            if matrix[row][col] == target:
                return True
            if matrix[row][col] < target:
                row += 1
            else:
                col -= 1
        
        return False

Java

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

JavaScript

var searchMatrix = function(matrix, target) {

    let row = 0;
    let col = matrix[0].length;
    while(row < matrix.length && col >= 0){
        if(matrix[row][col] === target){
            return true
        }
        if(matrix[row][col] < target){
            row++
        } else{
            col--
        }
    }
    
    return false;
};