What is the time complexity of Search a 2D Matrix?

The optimal solution has a time complexity of O(log(m*n)).

What data structures are used to solve Search a 2D Matrix?

This problem uses Array, Binary Search, Matrix. Understanding these concepts is essential for solving this Medium problem efficiently.

What are the key insights for solving Search a 2D Matrix?

Insight 1: The sorted nature of rows and the increasing order between rows allows us to treat the 2D matrix as a single, sorted 1D array. Insight 2: Binary search is the most suitable algorithm to achieve the required O(log(m*n)) time complexity.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Search a 2D Matrix - LeetCode 74 Solution

Q: Which companies ask LeetCode 74. Search a 2D Matrix in interviews?

This problem is frequently asked at Accenture, Adobe, Amazon, Apple, Arista Networks and 15 more companies.

Search a 2D Matrix - Complete Solution Guide

Search a 2D Matrix is LeetCode problem 74, a Medium level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

You are given an m x n integer matrix matrix with the following two 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. Given an integer target , return true if target is in matrix or false otherwise . You must write a solution in O(log(m * n)) time complexity. 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

Detailed Explanation

The problem asks us to search for a specific integer (`target`) within a 2D matrix (`matrix`). This matrix has two key properties: (1) each row is sorted in non-decreasing order, and (2) the first integer of each row is greater than the last integer of the previous row. We need to return `true` if the `target` exists in the matrix, and `false` otherwise. Crucially, the solution must have a time complexity of O(log(m*n)), where m is the number of rows and n is the number of columns.

Solution Approach

The solution uses binary search to efficiently find the `target` within the 2D matrix. By treating the matrix as a sorted 1D array, we can apply binary search. The algorithm iteratively narrows down the search range by comparing the middle element with the `target`. The core idea is to convert the 1D middle index `mid_idx` to its corresponding row and column indices in the 2D matrix using `row = mid_idx // n` and `col = mid_idx % n`, respectively. This allows us to access the element at `matrix[row][col]` and compare it with the target.

Step-by-Step Algorithm

Step 1: Initialize `left` to 0 and `right` to `m * n - 1`, representing the start and end indices of the flattened 2D matrix.
Step 2: While `left` is less than or equal to `right`, calculate the middle index `mid_idx = (left + right) // 2`.
Step 3: Convert the `mid_idx` to row and column indices using `row = mid_idx // n` and `col = mid_idx % n`, where `n` is the number of columns.
Step 4: Get the value at `matrix[row][col]`. If this value is equal to the `target`, return `true`.
Step 5: If the value at `matrix[row][col]` is less than the `target`, update `left = mid_idx + 1` to search in the right half.
Step 6: If the value at `matrix[row][col]` is greater than the `target`, update `right = mid_idx - 1` to search in the left half.
Step 7: If the loop finishes without finding the `target`, return `false`.

Key Insights

Insight 1: The sorted nature of rows and the increasing order between rows allows us to treat the 2D matrix as a single, sorted 1D array.
Insight 2: Binary search is the most suitable algorithm to achieve the required O(log(m*n)) time complexity.
Insight 3: Instead of explicitly creating a 1D array, we can use index manipulation to map 1D indices to 2D row and column indices during the binary search.

Complexity Analysis

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

Space Complexity: O(1)

Topics

This problem involves: Array, Binary Search, Matrix.

Companies

Asked at: Accenture, Adobe, Amazon, Apple, Arista Networks, Bloomberg, Cisco, Coupang, Goldman Sachs, Google, Grab, Meta, Microsoft, Nutanix, Snap, Tinkoff, Visa, Walmart Labs, Yahoo, Yandex.

Search a 2D Matrix | LeetCode 74

Medium

Array Binary Search Matrix

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

Solution Code

Available in:

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 midIdx = (left + right) / 2;
            int row = midIdx / n;
            int col = midIdx % n;
            int midVal = matrix[row][col];

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

        return false;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 74: Search a 2D Matrix - Detailed explanation and solution approaches.

Topics

Array Binary Search Matrix

Companies

AccentureAdobeAmazonAppleArista NetworksBloombergCiscoCoupang

Stats

Difficulty:Medium

Languages:4

Companies:20

Problem #:74

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

7 steps

1
Step 1: Initialize `left` to 0 and `right` to `m * n - 1`, representing the start and end indices of the flattened 2D matrix.
2
Step 2: While `left` is less than or equal to `right`, calculate the middle index `mid_idx = (left + right) // 2`.
3
Step 3: Convert the `mid_idx` to row and column indices using `row = mid_idx // n` and `col = mid_idx % n`, where `n` is the number of columns.
4
Step 4: Get the value at `matrix[row][col]`. If this value is equal to the `target`, return `true`.
5
Step 5: If the value at `matrix[row][col]` is less than the `target`, update `left = mid_idx + 1` to search in the right half.
6
Step 6: If the value at `matrix[row][col]` is greater than the `target`, update `right = mid_idx - 1` to search in the left half.
7
Step 7: If the loop finishes without finding the `target`, return `false`.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(log(m*n))

🚀 Logarithmic - Very efficient! Halves the problem each step.

💾

Space Complexity

O(1)

💪 Constant space - Uses same memory regardless of input!

📝

Why?

The binary search iterates until the `left` pointer crosses the `right` pointer. Each iteration effectively halves the search space of size m*n. Hence, the number of iterations (and thus the time complexity) is proportional to the logarithm of m*n, specifically log base 2 of (m*n). The space complexity is O(1) because the algorithm only uses a fixed number of variables regardless of the input size.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Linear Search

Iterate through each element of the matrix and compare it with the target. This is a brute-force approach.

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

Trade-offs: This approach is simpler to implement but much less efficient than binary search for large matrices. It should only be considered if the matrix is very small.

Row-wise Binary Search

Perform binary search on the first column to identify the target row (or potential rows). Then, apply binary search within that row to locate the target.

Time: O(log(m) + log(n)) which simplifies to O(log m + log n)Space: O(1)

Trade-offs: For scenarios where rows are significantly shorter than total element count, row-wise binary search may improve performance slightly (due to smaller search domain sizes at each stage) at the cost of extra logic.

✨

Key Insights

1Insight 1: The sorted nature of rows and the increasing order between rows allows us to treat the 2D matrix as a single, sorted 1D array.
2Insight 2: Binary search is the most suitable algorithm to achieve the required O(log(m*n)) time complexity.
3Insight 3: Instead of explicitly creating a 1D array, we can use index manipulation to map 1D indices to 2D row and column indices during the binary search.

📚

Key Terms Explained

For Students

Array

A collection of items stored at contiguous memory locations. Like a row of boxes.

Binary Search

Halving the search space each step. Like finding a word in a dictionary!

Edge Cases

Edge case 1: Empty matrix (`matrix` is null or empty, or `matrix[0]` is empty). The solution handles this by returning `false` at the beginning, preventing errors.
Edge case 2: Target is smaller than the smallest element or larger than the largest element in the matrix. The binary search algorithm will correctly narrow down the search space and eventually return `false` if the target is not found.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Incorrectly converting the 1D index to 2D row and column indices. Ensure you use integer division (`//` in Python, `/` in Java/C++) for the row and the modulo operator (`%`) for the column.

✗Common mistake 2: Not handling the edge case of an empty matrix, which can lead to errors when trying to access `matrix[0]`.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Searching for data in a sorted database table represented as a matrix. Database systems often use indexing and search algorithms similar to binary search to efficiently retrieve data.

🏦Real-world scenario 2: Finding a specific value in a lookup table where data is organized in a sorted manner. This can be used in image processing or data analysis applications.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

Consider multiple approaches before coding. Mentioning alternatives shows breadth of knowledge.

⚠️ Watch Out

Off-by-one errors are the most common mistake. Double-check your loop bounds and array indices.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: August 14, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

In a real interview, always clarify constraints first. Ask about input size and value ranges.

@TechLeadJul 13

Don't forget to handle the edge case when the input is empty. Many candidates miss this in interviews.

@DevExpert92Jul 6

❓

Frequently Asked Questions

What is the most efficient way to solve array problems?

Most array problems can be solved efficiently using techniques like two-pointer approach, sliding window, or hash maps. The key is identifying whether the array is sorted (enabling binary search) or if tracking seen elements (using hash maps) can help achieve O(n) time complexity.

How do I avoid off-by-one errors in binary search?

Use the pattern: left = 0, right = n-1, while (left <= right), mid = left + (right - left) / 2. Decide if you need to find exact match, first occurrence, or last occurrence, and adjust your conditions accordingly. Test with arrays of size 0, 1, and 2.

What techniques are commonly tested in medium-difficulty problems?

Medium problems often require combining multiple techniques: two-pointer with hash maps, BFS/DFS with state tracking, dynamic programming with optimization, or divide-and-conquer approaches. They test your ability to recognize patterns and choose the right combination of techniques.

How should I practice algorithm problems effectively?

Focus on understanding patterns rather than memorizing solutions. After solving a problem, review optimal solutions and understand the intuition. Group similar problems to recognize patterns. Practice explaining your approach out loud. Review problems after a few days to test retention.

What is the optimal approach for "Search a 2D Matrix"?

For this medium-level Array problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether binary search techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?