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

Difficulty: Medium

Problem Description

You are given an m x n integer matrix matrix with the following two properties:

  • Each row is sorted in non-decreasing order.
  • The first integer of each row is greater than the last integer of the previous row.

Given an integer target, return true if target is in matrix or false otherwise. You must write a solution in O(log(m * n)) time complexity.

Key Insights

  • The matrix is essentially a flattened sorted array because each row is sorted and the first element of each row is greater than the last element of the previous row.
  • We can utilize binary search to efficiently search the target value since the matrix is sorted.
  • The search space can be treated as a single-dimensional array where we calculate the corresponding row and column indices based on the mid-point of our binary search.

Space and Time Complexity

Time Complexity: O(log(m * n))
Space Complexity: O(1)

Solution

To solve this problem, we will use a binary search algorithm. We will treat the 2D matrix as a flattened 1D array. During the binary search, we will calculate the row and column indices based on the mid-point index. This allows us to check the value at the calculated position and adjust our search range accordingly until we find the target or exhaust the search space.

Code Solutions

def searchMatrix(matrix, target):
    if not matrix:
        return False
    
    m, n = len(matrix), len(matrix[0])
    left, right = 0, m * n - 1
    
    while left <= right:
        mid = left + (right - left) // 2
        mid_value = matrix[mid // n][mid % n]
        
        if mid_value == target:
            return True
        elif mid_value < target:
            left = mid + 1
        else:
            right = mid - 1
            
    return False
← Back to All Questions