Leetcode 74. Search a 2D Matrix

Problem

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

• Each row is sorted in ascending order from left to right
• The first integer of each row is strictly greater than the last integer of the previous row

This means if you were to "flatten" the entire matrix into a single array by concatenating all rows, you would get one long sorted array.

Write a function that determines whether a given target value exists anywhere in this matrix. Your solution should take advantage of the sorted structure to achieve better than linear time complexity.

Requirements

1. Return true if the target exists in the matrix, false otherwise
2. Optimize for time complexity by exploiting the sorted property
3. Handle edge cases including empty matrices, single elements, and single rows/columns

Constraints

• m == matrix.length (number of rows)
• n == matrix[i].length (number of columns)
• 1 <= m, n <= 100
• -10^4 <= matrix[i][j], target <= 10^4
• Each row is sorted in non-decreasing order
• The first element of each row is greater than the last element of the previous row (if it exists)
• Time complexity should be O(log(m × n))
• Space complexity should be O(1)

Examples

Example 1:

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3 Output: true Explanation: The value 3 is located in the first row at index 1

Example 2:

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13 Output: false Explanation: The value 13 does not exist in the matrix. It would fall between 11 and 16 if it were present

Example 3:

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 60 Output: true Explanation: The value 60 is at the last position of the matrix

Hint 1: Think 1D Since the matrix has the special property that each row's first element is greater than the previous row's last element, the entire matrix can be conceptually treated as a single sorted array. Can you map a 1D index to 2D coordinates?

Hint 2: Binary Search Binary search works on sorted data and runs in O(log n) time. If you treat the matrix as having m × n total elements indexed from 0 to m*n - 1, you can use binary search. Convert between 1D and 2D indices using: row = index // n and col = index % n.

Hint 3: Index Conversion For a matrix with n columns:

• To convert 1D index i to 2D coordinates: (i // n, i % n)
• To convert 2D coordinates (row, col) to 1D index: row * n + col

This allows you to perform binary search on the conceptual 1D array while accessing the actual 2D matrix.

Full Solution ` def searchMatrix(matrix, target): """ Search for a target value in a 2D matrix with sorted properties.

Time Complexity: O(log(m*n)) where m is rows and n is columns
Space Complexity: O(1) - only using a few variables
"""
if not matrix or not matrix[0]:
    return False

m = len(matrix)  # number of rows
n = len(matrix[0])  # number of columns

# Treat the 2D matrix as a 1D sorted array
# Binary search on the virtual 1D array
left = 0
right = m * n - 1

while left <= right:
    mid = (left + right) // 2
    
    # Convert 1D index to 2D coordinates
    row = mid // n
    col = mid % n
    
    mid_value = matrix[row][col]
    
    if mid_value == target:
        return True
    elif mid_value < target:
        # Target is in the right half
        left = mid + 1
    else:
        # Target is in the left half
        right = mid - 1

return False

`

Approach:

The key insight is recognizing that due to the matrix's properties (sorted rows + first element of each row greater than last element of previous row), we can treat it as one long sorted array without actually flattening it.

1. Setup: Calculate total elements as m × n and set up binary search boundaries (0 to m*n - 1)

2. Binary Search Loop: While the search space is valid:

   • Calculate the middle index in the virtual 1D array
   • Convert this 1D index to 2D matrix coordinates using division and modulo
   • Compare the value at that position with the target
   • Adjust search boundaries based on comparison

3. Index Conversion: For a matrix with n columns:

   • row = index // n (which row the element is in)
   • col = index % n (which column within that row)

Time Complexity: O(log(m × n)) - standard binary search on m × n elements

Space Complexity: O(1) - only using a constant number of variables

This approach is optimal because we're performing a single binary search over all elements rather than two separate binary searches (one for row, one for column) which would also work but is less elegant.

title: Search Sorted 2D Grid enableTestRunner: true testCases:

• name: "Target exists in middle" input: | matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3 output: "true" explanation: "The value 3 exists at position (0,1) in the matrix" functionName: searchMatrix args:

  • [[1,3,5,7],[10,11,16,20],[23,30,34,60]]
  • 3

• name: "Target does not exist" input: | matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13 output: "false" explanation: "The value 13 does not appear anywhere in the matrix" functionName: searchMatrix args:

  • [[1,3,5,7],[10,11,16,20],[23,30,34,60]]
  • 13

• name: "Single element matrix - found" input: | matrix = [[5]], target = 5 output: "true" explanation: "The single element matches the target" functionName: searchMatrix args:

  • [[5]]
  • 5

• name: "Single row matrix" input: | matrix = [[1,3,5,7,9]], target = 7 output: "true" explanation: "Target found in the single row at index 3" functionName: searchMatrix args:

  • [[1,3,5,7,9]]
  • 7

• name: "Target at boundaries" input: | matrix = [[1,2],[3,4],[5,6]], target = 6 output: "true" explanation: "Target is at the last position of the matrix" functionName: searchMatrix args:

  • [[1,2],[3,4],[5,6]]
  • 6 starterCode: python: | def searchMatrix(matrix, target): pass typescript: | function searchMatrix(matrix: number[][], target: number): boolean javascript: | function searchMatrix(matrix, target)

Problem

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

• Each row is sorted in ascending order from left to right
• The first integer of each row is strictly greater than the last integer of the previous row

This means if you were to "flatten" the entire matrix into a single array by concatenating all rows, you would get one long sorted array.

Write a function that determines whether a given target value exists anywhere in this matrix. Your solution should take advantage of the sorted structure to achieve better than linear time complexity.

Requirements

1. Return true if the target exists in the matrix, false otherwise
2. Optimize for time complexity by exploiting the sorted property
3. Handle edge cases including empty matrices, single elements, and single rows/columns

Constraints

• m == matrix.length (number of rows)
• n == matrix[i].length (number of columns)
• 1 <= m, n <= 100
• -10^4 <= matrix[i][j], target <= 10^4
• Each row is sorted in non-decreasing order
• The first element of each row is greater than the last element of the previous row (if it exists)
• Time complexity should be O(log(m × n))
• Space complexity should be O(1)

Examples

Example 1:

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3 Output: true Explanation: The value 3 is located in the first row at index 1

Example 2:

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13 Output: false Explanation: The value 13 does not exist in the matrix. It would fall between 11 and 16 if it were present

Example 3:

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 60 Output: true Explanation: The value 60 is at the last position of the matrix

Hint 1: Think 1D Since the matrix has the special property that each row's first element is greater than the previous row's last element, the entire matrix can be conceptually treated as a single sorted array. Can you map a 1D index to 2D coordinates?

Hint 2: Binary Search Binary search works on sorted data and runs in O(log n) time. If you treat the matrix as having m × n total elements indexed from 0 to m*n - 1, you can use binary search. Convert between 1D and 2D indices using: row = index // n and col = index % n.

Hint 3: Index Conversion For a matrix with n columns:

• To convert 1D index i to 2D coordinates: (i // n, i % n)
• To convert 2D coordinates (row, col) to 1D index: row * n + col

This allows you to perform binary search on the conceptual 1D array while accessing the actual 2D matrix.

Full Solution ` def searchMatrix(matrix, target): """ Search for a target value in a 2D matrix with sorted properties.

Time Complexity: O(log(m*n)) where m is rows and n is columns
Space Complexity: O(1) - only using a few variables
"""
if not matrix or not matrix[0]:
    return False

m = len(matrix)  # number of rows
n = len(matrix[0])  # number of columns

# Treat the 2D matrix as a 1D sorted array
# Binary search on the virtual 1D array
left = 0
right = m * n - 1

while left <= right:
    mid = (left + right) // 2
    
    # Convert 1D index to 2D coordinates
    row = mid // n
    col = mid % n
    
    mid_value = matrix[row][col]
    
    if mid_value == target:
        return True
    elif mid_value < target:
        # Target is in the right half
        left = mid + 1
    else:
        # Target is in the left half
        right = mid - 1

return False

`

Approach:

The key insight is recognizing that due to the matrix's properties (sorted rows + first element of each row greater than last element of previous row), we can treat it as one long sorted array without actually flattening it.

1. Setup: Calculate total elements as m × n and set up binary search boundaries (0 to m*n - 1)

2. Binary Search Loop: While the search space is valid:

   • Calculate the middle index in the virtual 1D array
   • Convert this 1D index to 2D matrix coordinates using division and modulo
   • Compare the value at that position with the target
   • Adjust search boundaries based on comparison

3. Index Conversion: For a matrix with n columns:

   • row = index // n (which row the element is in)
   • col = index % n (which column within that row)

Time Complexity: O(log(m × n)) - standard binary search on m × n elements

Space Complexity: O(1) - only using a constant number of variables

This approach is optimal because we're performing a single binary search over all elements rather than two separate binary searches (one for row, one for column) which would also work but is less elegant.