Search a 2D Matrix – 74. LeetCode

The Search a 2D Matrix problem involves finding a target value. The matrix has two key 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.

This structure makes the matrix conceptually similar to a 1D sorted array. The goal is to determine if the target exists in the matrix efficiently.

Brute Force Approach

public class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                if (matrix[i][j] == target) {
                    return true;
                }
            }
        }
        return false;
    }
}

• The brute force solution iterates through each element in the 2D matrix using nested loops. If the target is found, it returns true; otherwise, it completes the loops and returns false.

Optimal Approach: Binary Search

Algorithmic Pattern and Data Structure

This solution uses binary search, a classic divide-and-conquer algorithm. Since the matrix is sorted row-wise and column-wise, it can be treated as a virtual 1D array for binary search:

1. Map the 2D indices (row, col) to a 1D index.

2. Perform binary search on this virtual 1D array.

Steps of the Binary Search Algorithm

1. Treat the matrix as a virtual 1D array.

2. Initialize two pointers, left = 0 and right = m * n – 1.

3. While left <= right:

• Compute the middle index: mid = left + (right – left) / 2.

• Map mid to 2D indices: row = mid / n, col = mid \% n.

• Compare the matrix value at (row, col) with the target.

• Adjust left or right based on the comparison.

4. If the target is found, return true; otherwise, return false.

public class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int rows = matrix.length, cols = matrix[0].length;
        int left = 0, right = rows * cols - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2; // Avoid overflow
            int row = mid / cols; // Map 1D index to row
            int col = mid % cols; // Map 1D index to col
            int midValue = matrix[row][col];

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

Line-By-Line Explanation

Step 1: Input Dimensions

int rows = matrix.length, cols = matrix[0].length;

• These dimensions are used to map between 1D and 2D indices and to determine the total number of elements in the matrix.
• Avoids hardcoding matrix dimensions, which could cause bugs or limit usability.

Step 2: Define the Search Range

int left = 0, right = rows * cols - 1;

• left: Represents the start index of the search range in the virtual 1D array.
• right: Represents the last index in the virtual 1D array, calculated as rows x cols – 1.
• Binary search operates on a sorted array, so this sets the bounds of the search space.
• The matrix is conceptually flattened into a 1D array.

Step 3: Binary Search Loop

while (left <= right) {

• Keeps iterating until the search space is exhausted.

Step 4: Calculate Midpoint

int mid = left + (right - left) / 2; // Avoid overflow

• Calculate the middle index of the current search engine
• Preventing overflow ensures the code works correctly for large matrices.

Step 5: Map Midpoint to Matrix Indices

int row = mid / cols; // Map 1D index to row
int col = mid % cols; // Map 1D index to col

• Converts the 1D index (mid) into 2D matrix coordinates (row, col).
• row = mid / cols determine the row number.
• col = mid % cols determines the column number within that row.

• Efficiently maps between the conceptual 1D and 2D representations without extra memory.

Step 6: Access the Middle Value

int midValue = matrix[row][col];

• Retrieves the value at the calculated row and col in the matrix.

Step 7: Compare the Midpoint with Target

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

• If middle value equals the target, the search is complete, and true is returned.
• If the middle value is lass than the target, narrow search range in the right half.
• If the middle value is greater than the target, narrow the search range to the left half.
• Directly reduces the search space by half in each iteration.

Step 8: Return

return false;

• Ensures the function always returns a result.

Why This Code Works

The binary search algorithm for Search a 2D Matrix is highly efficient, reducing time complexity to O(\log(m \times n)) by leveraging the matrix’s sorted structure. It uses robust techniques like overflow-safe midpoint calculation and cleanly maps 1D indices to 2D coordinates, ensuring correctness and clarity. With O(1) space complexity and adaptability to large datasets, this solution is both practical and elegant, exemplifying optimal algorithm design.