Search in a 2 D matrix

Problem Overview

The problem "Search a 2D Matrix" on LeetCode involves searching for a target value in a 2D matrix. The matrix has the following properties:

• Integers in each row are sorted in ascending order from left to right.
• The first integer of each row is greater than the last integer of the previous row.

The task is to write an efficient algorithm to determine whether a target value exists in this matrix or not.

Understanding the Problem

Given a matrix with the aforementioned properties, you are required to efficiently determine if a target value exists within it. The challenge lies in leveraging the sorted nature of both the rows and the entire matrix to minimize the number of comparisons needed to find the target value.

Example

Input:

matrix = [
  [1, 3, 5, 7],
  [10, 11, 16, 20],
  [23, 30, 34, 60]
]
target = 3

Output: true

Explanation: 3 is found in the first row.

Key DSA Concepts and Theory

Binary Search

Binary Search is a powerful technique often used when dealing with sorted arrays. It operates by dividing the search interval in half repeatedly, allowing it to locate an element in (O(\log n)) time. For a 1D sorted array, this means continually narrowing down the search to the half that may contain the element.

For our problem, the matrix can be considered as a single sorted list, thus allowing for a 2D application of binary search by treating it as a 1D array.

Solution Approach

Approach

1. Transform Index Calculation: Treat the matrix as a single sorted list by calculating the mid-point based on the entire matrix size rather than just the rows or columns.
2. Binary Search Application: Apply binary search to this 1D representation by calculating the row and column from the mid-point index.
3. Iterate Until Found or Interval is Empty: Continue the process until the target is found or the search interval is exhausted.

Detailed Step-by-Step Guide

C++ Implementation

#include <vector>
using namespace std;

bool searchMatrix(vector<vector<int>>& matrix, int target) {
    if (matrix.empty() || matrix[0].empty()) {
        return false;
    }
    
    int rows = matrix.size();
    int cols = matrix[0].size();
    int left = 0, right = rows * cols - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        int mid_value = matrix[mid / cols][mid % cols];
        
        if (mid_value == target) {
            return true;
        } else if (mid_value < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return false;
}

Java Implementation

public class Solution {
    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, right = rows * cols - 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int midValue = matrix[mid / cols][mid % cols];
            
            if (midValue == target) {
                return true;
            } else if (midValue < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return false;
    }
}

Time and Space Complexity Analysis

• Time Complexity: The time complexity of this solution is (O(\log (m \times n))), where (m) is the number of rows and (n) is the number of columns. This is due to the logarithmic reduction of the search space in each step of the binary search.

• Space Complexity: The space complexity is (O(1)), as no additional space proportional to the input size is used apart from constant placeholders.

Common Mistakes to Avoid

• Index Calculation Errors: Ensure that indexing is done correctly when the matrix is treated as a linear array. Miscomputing the index conversion from 1D to 2D (and vice versa) can lead to incorrect results.

• Empty Matrix Check: Before proceeding with binary search, verifying that the matrix is not empty prevents out-of-bounds errors.

Similar Problems on Leetcode

• Search a 2D Matrix II (Question 240)
• Find Minimum in Rotated Sorted Array (Question 153)

Additional Resources and References

• Binary Search Tutorial
• Matrix Manipulation in Programming

This concludes the article on solving the "Search a 2D Matrix" problem using Binary Search on a conceptual 1D array derived from the matrix. This efficient approach helps in leveraging the problem constraints to find the solution swiftly.