Algorithm Day65 - Search a 2D Matrix

Posted on In , Views:

🧩 Problem Description

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

  1. Each row is sorted in ascending order.
  2. The first integer of each row is greater than the last integer of the previous row.

Given an integer target, return true if target is in the matrix or false otherwise.

💬 Examples

Example 1

1
2
Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true

Example 2

1
2
Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Output: false

💡 Intuition

The matrix has a special structure:

  • If we flatten it into a single array, it is fully sorted.
  • Thus, we can apply binary search over the virtual array.

Mapping from index in flattened array:

  • row = mid / n
  • col = mid % n
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length, n = matrix[0].length;
        int left = 0, right = m * n - 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int value = matrix[mid / n][mid % n];
            if (value == target) {
                return true;
            } else if (value < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return false;
    }
}

⏱ Complexity Analysis

  • Time: O(log(m × n)) — binary search on m*n elements.
  • Space: O(1) — only pointers are used.

✍️ Summary

  • Flatten the 2D matrix into a sorted 1D array conceptually.
  • Apply binary search on indices.

Related problems

  • lc-240 — Search a 2D Matrix II
  • lc-33 — Search in Rotated Sorted Array