We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Search a 2D Matrix II

Difficulty: Medium

Problem Description

Write an efficient algorithm that searches for a value target in an m x n integer matrix 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.

Key Insights

  • The search space can be reduced by utilizing the sorted properties of the matrix.
  • Starting from the top-right corner of the matrix allows for an efficient search strategy: if the current number is greater than the target, move left; if it is less, move down.
  • This eliminates an entire row or column with each comparison, leading to a time complexity of O(m + n).

Space and Time Complexity

Time Complexity: O(m + n)
Space Complexity: O(1)

Solution

The algorithm starts at the top-right corner of the matrix. Depending on the comparison between the current element and the target, it either moves left or down. This approach effectively reduces the search space with each step, leveraging the sorted nature of the matrix.

Code Solutions

def searchMatrix(matrix, target):
    if not matrix or not matrix[0]:
        return False
    
    rows, cols = len(matrix), len(matrix[0])
    row, col = 0, cols - 1  # Start from the top-right corner

    while row < rows and col >= 0:
        current = matrix[row][col]
        if current == target:
            return True  # Target found
        elif current > target:
            col -= 1  # Move left
        else:
            row += 1  # Move down

    return False  # Target not found
← Back to All Questions