LeetCode 74: Search a 2D Matrix, Java Solution

Searching for an element in an array is as simple as examining every element until we find our target. The brute force approach gives us a runtime complexity of O(n), where n is the number of elements in the array. Expanding this idea out into a 2-dimensional array is relatively straight forward too. Just iterate through each row and column one by one, until you find your desired value. This type of search gives a Big O of O(m * n), with m being the number of rows and n is the number of columns. However, the description in this problem asks us to achieve a runtime complexity of O(log(m * n)). We will examine how to achieve this optimized search complexity in this article!

Overview

To solve this problem with a time complexity of O(log(m * n), we can treat the 2D matrix as a 1D sorted array. Since each row in the matrix is sorted, and the first integer of every row is greater than the last integer of the previous row, the matrix can be considered as a flattened sorted list.

Here’s how you can approach the problem:

Flatten the 2D array: Treat the matrix as a single sorted array.
Binary Search: Apply binary search to find the target in this virtual array.

Problem Statement

You are given an m x n 2D matrix of integers and a target value. The matrix has the following properties:

Each row is sorted in non-decreasing order.
The first integer of each row is greater than the last integer of the previous row.

Your task is to determine if the target exists within the matrix. The goal is to implement a solution that runs in O(log⁡(m*n)) time.

Example

Consider the following 3 x 4 matrix:

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

Suppose we want to find the target value 16.

Solution Explanation

Given the matrix properties, we can treat the 2D matrix as a single flattened 1D sorted array. The flattened version of the matrix would look like this:

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

Each index in this flattened array corresponds to an element in the original matrix, which can be mapped using the following formulas:

Row Calculation: row = mid / n
Column Calculation: col = mid % n

Where mid is the index in the flattened array, and n is the number of columns in the matrix.

Example Calculations

Binary Search:

Initialize left = 0 and right = m * n - 1 (which is 11 for this matrix).
Compute the middle index: mid = (left + right) / 2. For the first iteration, mid = (0 + 11) / 2 = 5.
Map mid = 5 back to 2D coordinates:
- row = 5 / 4 = 1
- col = 5 % 4 = 1
This corresponds to matrix[1][1] = 11.
Since 11 is less than the target 16, we adjust our search range to the right half by setting left = mid + 1.

Continue Search:

Calculate new mid: mid = (6 + 11) / 2 = 8.
Map mid = 8 back to 2D coordinates:
- row = 8 / 4 = 2
- col = 8 % 4 = 0
This corresponds to matrix[2][0] = 23.
Since 23 is greater than 16, adjust the search range to the left half by setting right = mid - 1.

Final Iteration:

Calculate new mid: mid = (6 + 7) / 2 = 6.
Map mid = 6 back to 2D coordinates:
- row = 6 / 4 = 1
- col = 6 % 4 = 2
This corresponds to matrix[1][2] = 16, which matches our target. We return true.

Code Implementation In Java

    public boolean searchMatrix(int[][] matrix, int target) {
        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;
    }

Explanation

Binary Search Logic:
- The algorithm treats the matrix as a flattened array and performs binary search to find the target.
- row = mid / n and col = mid % n are used to map the middle index back to the matrix.
Time Complexity:
- This approach runs in O(log⁡(m*n)) time because it’s based on binary search, which halves the search space at each step.

Summary

This solution efficiently searches a 2D matrix by leveraging its sorted properties and using binary search. The approach is optimal for matrices with the given properties, ensuring that the search operation is performed in logarithmic time.

Contents