Katkat
Back

Search for a Value in a Matrix Sorted as One Continuous Sequence

AmazonSoftware Engineer · Other
MediumSoftware EngineerOtherCoding & Algorithms

Last updated

Decide whether a target value appears in a matrix whose rows are sorted and whose every row starts above the previous row's last value. It tests exploiting that ordering to search in logarithmic time and handling single-row, repeated-value and boundary cases correctly.

You are given an m x n integer matrix with two ordering properties: every row is sorted in non-decreasing order, and the first value of each row is strictly greater than the last value of the row above it. Decide whether a given target appears anywhere in the matrix.

Function Signature

def matrix_contains(matrix: List[List[int]], target: int) -> bool:

Rules

  • Return True if at least one cell equals target, otherwise False.
  • The input always satisfies both ordering properties; you do not need to validate it.
  • Aim for running time logarithmic in m * n.

Constraints

  • m == len(matrix), n == len(matrix[i]) for every row, all rows have the same length
  • 1 <= m <= 100 and 1 <= n <= 100
  • -10^4 <= matrix[i][j] <= 10^4
  • -10^4 <= target <= 10^4

Examples

Example 1

Input: matrix = [[2, 4, 9], [11, 15, 18], [21, 30, 41]], target = 15
Output: True

Example 2

Input: matrix = [[2, 4, 9], [11, 15, 18], [21, 30, 41]], target = 10
Output: False

10 would fall between the end of the first row (9) and the start of the second row (11), so it is not present.

Example 3

Input: matrix = [[-3, -3, 0]], target = -3
Output: True

Rows may contain repeated values.