algoadvance

The 240. Search a 2D Matrix II problem on LeetCode requires you to search for a given target value in an m x n integer 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.

You need to write a function searchMatrix(matrix, target) to determine if target is in the matrix.

Example 1:

Input: matrix = [[1,4,7,11,15],
                 [2,5,8,12,19],
                 [3,6,9,16,22],
                 [10,13,14,17,24],
                 [18,21,23,26,30]],
       target = 5
Output: true

Example 2:

Input: matrix = [[1,4,7,11,15],
                 [2,5,8,12,19],
                 [3,6,9,16,22],
                 [10,13,14,17,24],
                 [18,21,23,26,30]],
       target = 20
Output: false

Clarifying Questions

1. Are there any constraints on the size of the matrix?
   • Yes, typically m and n can be large, like up to 300.
2. Can the matrix contain duplicate elements?
   • No, according to problem description each element appears only once.

Strategy

1. Leveraging Matrix Properties: Start from the bottom-left corner of the matrix.
2. Comparison and Move: At each step, compare the current element with the target:
   • If the current element is greater than the target, move up (decrease row index).
   • If the current element is less than the target, move right (increase column index).
3. Termination: Continue the above steps until you either find the target or move out of the bounds of the matrix.

Code

def searchMatrix(matrix, target):
    if not matrix or not matrix[0]:
        return False
    
    rows = len(matrix)
    cols = len(matrix[0])
    
    row = rows - 1  # Start from the bottom-left corner
    col = 0
    
    while row >= 0 and col < cols:
        if matrix[row][col] == target:
            return True
        elif matrix[row][col] > target:
            row -= 1
        else:
            col += 1
    
    return False

Time Complexity

• Time Complexity: O(m + n)
  • In the worst case, you might traverse all the way from the bottom-left to the top-right, hence visiting m + n elements.
• Space Complexity: O(1)
  • The solution uses a constant amount of extra space.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?