algoadvance

Leetcode 74. Search a 2D Matrix

Problem Statement

You are given a matrix matrix with m rows and n columns, and an integer target. The matrix has the following properties:

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

Write an efficient algorithm that searches for a value in the matrix. Return true if the value is found, and false otherwise.

Example 1:

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

Example 2:

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

Clarifying Questions

  1. Are there any constraints on the values within the matrix?
    • Each row and column can contain positive and negative integers.
  2. What should be the behavior if the matrix is empty?
    • If the matrix is empty, the function should return false.
  3. Can rows or columns have duplicate entries?
    • No, each row and each column is sorted in ascending order without duplicates as per the problem statement.

Strategy

Given that the matrix is sorted in a specific way, each row starts with a number larger than the last number of the previous row and within each row, the numbers are sorted. This makes it similar to a 1D sorted array and suggests that we can use a binary search algorithm:

  1. Flatten the Matrix Conceptually: Consider the entire 2D matrix as a single sorted 1D array.
  2. Binary Search: Use binary search to find the target. However, during the search, map the “1D” index back to 2D indices to access the actual matrix elements.

Detailed Steps:

  1. Compute the total number of elements in the matrix: totalElements = m * n.
  2. Use two pointers (left at 0 and right at totalElements - 1) for the binary search.
  3. Calculate the middle index and map it back to the 2D matrix indices:
    • 2D row index: middle / n (integer division)
    • 2D column index: middle % n (remainder)
  4. Compare the matrix value at the middle index to the target.
    • If it equals the target, return true.
    • If it is less than target, move left to middle + 1.
    • If it is greater than target, move right to middle - 1.
  5. Continue until left exceeds right.
  6. If the loop ends and the target hasn’t been found, return false.

Code

#include <vector>
using namespace std;

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if (matrix.empty() || matrix[0].empty()) {
            return false;
        }
        
        int m = matrix.size();
        int n = matrix[0].size();
        int left = 0;
        int right = m * n - 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int midValue = matrix[mid / n][mid % n];
            
            if (midValue == target) {
                return true;
            } else if (midValue < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return false;
    }
};

Time Complexity

The time complexity of this approach is O(log(m * n)), since we are using binary search on a range that contains m * n elements.

The space complexity is O(1) because we are only using a few additional variables that do not scale with input size.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI