4.5 Search a 2D Matrix

4.5.1 Problem Metadata

4.5.2 Description

Each row of the matrix is sorted, and the first element of each row is greater than the last element of the previous row. Determine if a target value exists in the matrix.

4.5.3 Examples

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

4.5.4 Constraints

  • 1 <= m, n <= 100
  • Matrix entries are integers

4.5.5 Solution - Treat as 1D

4.5.5.1 Walkthrough

Because every row starts after the prior row ends, we can treat the matrix as a flattened sorted array of length m * n. Perform binary search using virtual indices; convert a mid index back to row/col by division and modulus.

4.5.5.2 Analysis

  • Time Complexity: O(log(m * n))
  • Space Complexity: O(1)

4.5.5.3 Implementation Steps

  1. Let low = 0, high = m * n - 1.
  2. While low <= high:
    1. mid = (low + high) / 2.
    2. Map to row = mid / n, col = mid % n.
    3. Compare matrix[row][col] with target and adjust bounds.
  3. Return false if not found.

4.5.5.4 Code - Java

public boolean searchMatrix(int[][] matrix, int target) {
    if (matrix.length == 0 || matrix[0].length == 0) {
        return false;
    }

    int rows = matrix.length;
    int cols = matrix[0].length;
    int left = 0;
    int right = rows * cols - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;
        int r = mid / cols;
        int c = mid % cols;
        int value = matrix[r][c];

        if (value == target) {
            return true;
        } else if (value < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return false;
}

4.5.5.5 Code - Go

func searchMatrix(matrix [][]int, target int) bool {
    if len(matrix) == 0 || len(matrix[0]) == 0 {
        return false
    }

    rows := len(matrix)
    cols := len(matrix[0])
    l := 0
    r := rows * cols - 1

    for l <= r {
        mid := l + (r - l) / 2
        row := mid / cols
        col := mid % cols
        val := matrix[row][col]

        if val == target {
            return true
        } else if val < target {
            l = mid + 1
        } else {
            r = mid - 1
        }
    }

    return false
}

4.5.6 Solution 2 - Row-First Linear Search

4.5.6.1 Walkthrough

Instead of treating the matrix as a flattened 1D array, we can leverage the sorted property more directly:

  1. Find the target row: Linear scan through rows to find which row could contain the target by checking if the target falls between the first and last element of that row.
  2. Search within the row: Once the correct row is identified, perform a linear search within that row.

This approach is more intuitive and easier to understand than the binary search coordinate mapping, though it has worse time complexity.

4.5.6.2 Analysis

  • Time Complexity: O(m + n) where m is the number of rows and n is the number of columns. In the worst case, we scan all m rows to find the target row, then scan all n columns within that row.
  • Space Complexity: O(1)

Trade-offs vs Solution 1: - Pros: Simpler logic, no coordinate arithmetic, easier to understand and debug - Cons: Slower (O(m + n) vs O(log(m × n))), not optimal for large matrices - Best for: Small matrices, interview scenarios where clarity is prioritized over optimal time complexity

4.5.6.3 Implementation Steps

  1. Iterate through each row to find which row contains the target:
    • Check if matrix[i][0] <= target <= matrix[i][cols-1]
    • If true, save the row index and break
  2. If no valid row found (row remains -1), return false
  3. Linear search through the identified row:
    • If any element equals target, return true
  4. If not found after scanning the row, return false

4.5.6.4 Code - Go

func searchMatrix(matrix [][]int, target int) bool {
    rows := len(matrix)
    cols := len(matrix[0])

    row := -1
    // Find which row could contain the target
    for i := 0; i < rows; i++ {
        // Check if target is between first and last element of row i
        if matrix[i][0] <= target && matrix[i][cols-1] >= target {
            row = i
            break
        }
    }

    // Target row not found
    if row < 0 {
        return false
    }

    // Linear search within the identified row
    for j := 0; j < cols; j++ {
        if matrix[row][j] == target {
            return true
        }
    }

    return false
}