LeetCode 74: Search a 2D Matrix Solution

Master LeetCode problem 74 (Search a 2D Matrix), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

74. Search a 2D Matrix

Medium

Array Binary Search Matrix

Problem Explanation

Explanation

To solve this problem in O(log(m * n)) time complexity, we can visualize the 2D matrix as a 1D array and perform a modified binary search. We can treat the matrix as a sorted list and apply binary search on it while converting the mid index to a 2D position. By doing this, we can efficiently search for the target value in the matrix.

Initialize pointers left = 0 and right = m * n - 1, where m is the number of rows and n is the number of columns in the matrix.
Perform binary search on the matrix:
- Calculate the mid index as (left + right) / 2.
- Convert mid index to 2D position as midRow = midIndex / n and midCol = midIndex % n.
- Compare the target value with matrix[midRow][midCol] and adjust the pointers accordingly.
Return true if the target is found, false otherwise.

Time Complexity: O(log(m * n))
Space Complexity: O(1)

Solution Code

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0) {
            return false;
        }
        
        int m = matrix.length;
        int n = matrix[0].length;
        
        int left = 0, right = m * n - 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int midRow = mid / n;
            int midCol = mid % n;
            
            if (matrix[midRow][midCol] == target) {
                return true;
            } else if (matrix[midRow][midCol] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return false;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 74 (Search a 2D Matrix)?

This page provides optimized solutions for LeetCode problem 74 (Search a 2D Matrix) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 74 (Search a 2D Matrix)?

The time complexity for LeetCode 74 (Search a 2D Matrix) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 74 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 74 in Java, C++, or Python.

Back to LeetCode Solutions