Search a 2D Matrix II - Python Solution

1. Introduction

"Search a 2D Matrix II" is a problem that combines matrix traversal with binary search principles. The challenge lies in efficiently searching for a target value in a 2D matrix where each row and each column is sorted in ascending order. This problem tests the ability to apply search algorithms in a two-dimensional space with sorted data.

Problem

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, write an efficient algorithm to search for a target value in the matrix. The algorithm should return true if the target is found and false otherwise.

2. Solution Steps

1. Start with the top right corner of the matrix.

2. If the target is greater than the current element, move down a row.

3. If the target is less than the current element, move left a column.

4. Repeat steps 2 and 3 until the target is found or the bounds of the matrix are exceeded.

5. Return true if the target is found, otherwise false.

3. Code Program

def searchMatrix(matrix, target):
    if not matrix:
        return False

    rows, cols = len(matrix), len(matrix[0])
    row, col = 0, cols - 1

    while row < rows and col >= 0:
        if matrix[row][col] == target:
            return True
        elif matrix[row][col] < target:
            row += 1
        else:
            col -= 1

    return False

# Example Usage
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]
]
print(searchMatrix(matrix, 5))  # Output: True
print(searchMatrix(matrix, 20)) # Output: False

Output:

True
False

Explanation:

1. Matrix Properties: Utilizes the properties of the matrix having sorted rows and columns.

2. Efficient Search: Begins the search from the top right corner, allowing elimination of either a row or a column in each step.

3. Directional Movement: Moves either down (if the target is larger) or left (if the target is smaller).

4. Termination: The search terminates when the target is found or when the search space is exhausted.

5. Optimized Algorithm: Provides an O(m + n) time complexity solution, more efficient than a brute force approach.

6. Result: Returns true if the target is found in the matrix, otherwise false.