Search In Sorted Matrix

Category: Searching

Difficulty: Medium

Description

You're given a two-dimensional array (a matrix) of distinct integers and a target integer. Each row in the matrix is sorted, and each column is also sorted; the matrix doesn't necessarily have the same height and width.

Write a function that returns an array of the row and column indices of the target integer if it's contained in the matrix, otherwise [-1, -1].

Sample Input

matrix = [
  [1, 4, 7, 12, 15, 1000],
  [2, 5, 19, 31, 32, 1001],
  [3, 8, 24, 33, 35, 1002],
  [40, 41, 42, 44, 45, 1003],
  [99, 100, 103, 106, 128, 1004],
]
target = 44

Sample Output

[3, 3]

Optimal Space & Time Complexity

O(n + m) time | O(1) space - where n is the length of the matrix's rows and m is the length of the matrix's columns