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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Search a 2D Matrix II

Number: 240

Difficulty: Medium

Paid? No

Companies: Google, Amazon, Meta, Microsoft, PayPal, Oracle, ByteDance, Apple, Adobe, Snap, Uber

Problem Description

Given an m x n integer matrix where each row is sorted in ascending order from left to right and each column is sorted in ascending order from top to bottom, determine if the target integer exists in the matrix.

Key Insights

  • Each row and column is sorted, which allows us to eliminate multiple rows or columns with one comparison.
  • Starting from the top-right corner (or bottom-left) is beneficial because at this position, one can decide to move left or down based on how the current value compares with the target.
  • This "staircase" search leads to a linear time algorithm relative to the sum of dimensions of the matrix.

Space and Time Complexity

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

Solution

The algorithm starts from the top-right corner of the matrix. At each step, compare the current element with the target:

  • If the current element equals the target, return true.
  • If the current element is greater than the target, move left because all elements below are larger.
  • If the current element is smaller than the target, move down because all elements to the left are smaller. This method ensures that in each step one row or one column is eliminated from consideration, leading to an efficient search.

Code Solutions

# Python implementation with detailed comments

def searchMatrix(matrix, target):
    # If the matrix is empty, return False
    if not matrix or not matrix[0]:
        return False

    # Set initial position to top-right corner of the matrix
    row, col = 0, len(matrix[0]) - 1

    # Iterate until we either find the target or exhaust the matrix bounds
    while row < len(matrix) and col >= 0:
        # Store the current element
        current = matrix[row][col]
        # Check if the current element is equal to target
        if current == target:
            return True
        # If the current element is greater, move left
        elif current > target:
            col -= 1
        # If smaller, move down
        else:
            row += 1

    # Target was not found
    return False
← Back to All Questions