Search a 2D Matrix - Video Solutions

Problem Overview: You are given an m x n matrix where each row is sorted in ascending order and the first element of each row is greater than the last element of the previous row. The task is to determine whether a given target value exists in the matrix.

Approach 1: Linear Scan (O(m * n) time, O(1) space)

The most direct method is to iterate through every element in the matrix and compare it with the target. Use nested loops: the outer loop scans rows and the inner loop scans columns. The algorithm stops early if the target is found. This approach requires no additional data structures and works for any matrix layout, but it ignores the sorted structure of the matrix and performs unnecessary comparisons.

Time complexity is O(m * n) because every cell may be visited in the worst case. Space complexity is O(1). This approach is useful only as a baseline or when the matrix is extremely small.

Approach 2: Two-step Binary Search (O(log m + log n) time, O(1) space)

The matrix ordering provides a key observation: the first column effectively acts like a sorted list of row ranges. First perform a binary search on rows to find the row that could contain the target. Compare the target with the first and last elements of each candidate row to narrow the search. Once the correct row is identified, run a second binary search on that row to locate the target value.

This method leverages properties of both binary search and sorted arrays. The first search takes O(log m) time and the second takes O(log n). Space complexity remains O(1) since the search operates directly on the matrix.

Approach 3: Binary Search Treating Matrix as 1D (O(log(m * n)) time, O(1) space)

Because each row's first element is greater than the previous row's last element, the entire matrix behaves like a single sorted array. Treat the matrix as a virtual 1D array of length m * n. During binary search, convert the midpoint index into matrix coordinates using row = mid / n and col = mid % n.

This removes the need for two separate searches and performs a single O(log(m * n)) binary search. Only index arithmetic is required, so space complexity stays O(1). This technique is a common pattern when working with sorted matrix problems.

Recommended for interviews: Interviewers typically expect the binary search solution that treats the matrix as a flattened sorted array. It demonstrates that you recognize the global ordering property and can map 1D indices to 2D coordinates efficiently. Starting with the brute force scan shows baseline reasoning, but the O(log(m * n)) approach demonstrates strong algorithmic thinking.