algoadvance

Leetcode 74. Search a 2D Matrix

Problem Statement

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

You need to determine whether a target integer exists in the matrix or not.

Example:

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

Output: true

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

Output: false

Clarifying Questions

  1. Can the matrix be empty?
  2. Are there any constraints on the values in the matrix (e.g., only positive integers)?

Strategy

The matrix properties indicate that it can be treated as a sorted array if we map its indices cleverly. To leverage this, we will use a binary search approach.

Steps:

  1. Treat the matrix as a virtual sorted array.
  2. Use binary search on this virtual array.
  3. To translate the 1D binary search index to a 2D matrix index:
    • For row index: row = mid / n (integer division)
    • For column index: col = mid % n (remainder)

Time Complexity

Code

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

        int m = matrix.length;
        int n = matrix[0].length;
        int left = 0;
        int right = m * n - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            int midElement = matrix[mid / n][mid % n];

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

        return false;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[][] matrix = {
                {1, 3, 5, 7},
                {10, 11, 16, 20},
                {23, 30, 34, 60}
        };
        System.out.println(sol.searchMatrix(matrix, 3));   // true
        System.out.println(sol.searchMatrix(matrix, 13));  // false
    }
}

Explanation

  1. Boundary Check: If the matrix is empty or any of its dimensions is zero, immediately return false.
  2. Binary Search Initialization: Initialize left as 0 and right as m * n - 1 to cover the entire virtual array.
  3. Binary Search Loop:
    • Compute middle index mid and find the corresponding element in the matrix using matrix[mid / n][mid % n].
    • Check if this middle element matches the target.
    • Adjust the search range based on whether the middle element is less than or greater than the target.
  4. If the element is found, return true; otherwise, return false after the loop completes.

The approach ensures efficient searching with a logarithmic time complexity.

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