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

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

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

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

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

Insight 1: The sorted nature of rows and columns allows for an efficient search strategy, avoiding a naive O(m*n) traversal. Insight 2: Starting the search from the top-right corner or bottom-left corner allows for eliminating either a row or a column in each comparison.

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

Search a 2D Matrix II - LeetCode 240 Solution

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

This problem is frequently asked at ByteDance, Citadel, Coupang, MakeMyTrip, Oracle and 4 more companies.

Search a 2D Matrix II - Complete Solution Guide

Search a 2D Matrix II is LeetCode problem 240, 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

Write an efficient algorithm that searches for a value target in an m x n integer matrix matrix . This matrix has the following properties: Integers in each row are sorted in ascending from left to right. Integers in each column are sorted in ascending from top to bottom. Example 1: Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5 Output: true Example 2: Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,

Detailed Explanation

The problem asks us to search for a specific `target` value within a 2D integer matrix. The matrix has two crucial properties: each row is sorted in ascending order from left to right, and each column is sorted in ascending order from top to bottom. We need to design an efficient algorithm to determine if the `target` exists in the matrix and return `true` if it does, otherwise `false`. The constraints specify the dimensions of the matrix and the range of values within the matrix and the target.

Solution Approach

The provided solutions use a 'staircase search' or 'ZigZag search' approach, which leverages the sorted nature of both rows and columns. The algorithm starts at the top-right corner of the matrix. If the current element is equal to the target, the search is successful. If the current element is greater than the target, it means the target cannot be in the current column (because all elements below are even larger), so we move to the left. If the current element is smaller than the target, it means the target cannot be in the current row (because all elements to the left are even smaller), so we move down. We repeat this process until the target is found or we go out of bounds.

Step-by-Step Algorithm

Step 1: Check for empty matrix. If the matrix is empty, return `false` immediately.
Step 2: Initialize `row` to 0 (the first row) and `col` to `cols - 1` (the last column).
Step 3: While `row` is within the matrix bounds (`row < rows`) and `col` is within the matrix bounds (`col >= 0`), perform the following:
Step 4: Get the value of the current element `matrix[row][col]`.
Step 5: If `current == target`, return `true`.
Step 6: If `current > target`, it means the target cannot be in the current column, so decrement `col` by 1 (move left).
Step 7: If `current < target`, it means the target cannot be in the current row, so increment `row` by 1 (move down).
Step 8: If the loop finishes without finding the target, return `false`.

Key Insights

Insight 1: The sorted nature of rows and columns allows for an efficient search strategy, avoiding a naive O(m*n) traversal.
Insight 2: Starting the search from the top-right corner or bottom-left corner allows for eliminating either a row or a column in each comparison.
Insight 3: The problem can be viewed as a modified binary search. Instead of bisecting a single array, we are effectively bisecting the search space in two dimensions by either moving to the next row or the previous column

Complexity Analysis

Time Complexity: O(m+n)

Space Complexity: O(1)

Topics

This problem involves: Array, Binary Search, Divide and Conquer, Matrix.

Companies

Asked at: ByteDance, Citadel, Coupang, MakeMyTrip, Oracle, PayPal, Snap, Whatnot, tcs.

Search a 2D Matrix II | LeetCode 240

Medium

Array Binary Search Divide and Conquer Matrix

Time: O(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 rows = matrix.length;
        int cols = matrix[0].length;

        int row = 0;
        int col = cols - 1;

        while (row < rows && col >= 0) {
            int current = matrix[row][col];
            if (current == target) {
                return true;
            } else if (current > target) {
                col -= 1;
            } else {
                row += 1;
            }
        }

        return false;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

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

Topics

Array Binary Search Divide and Conquer Matrix

Companies

ByteDanceCitadelCoupangMakeMyTripOraclePayPalSnapWhatnot

Stats

Difficulty:Medium

Languages:4

Companies:9

Problem #:240

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

8 steps

1
Step 1: Check for empty matrix. If the matrix is empty, return `false` immediately.
2
Step 2: Initialize `row` to 0 (the first row) and `col` to `cols - 1` (the last column).
3
Step 3: While `row` is within the matrix bounds (`row < rows`) and `col` is within the matrix bounds (`col >= 0`), perform the following:
4
Step 4: Get the value of the current element `matrix[row][col]`.
5
Step 5: If `current == target`, return `true`.
6
Step 6: If `current > target`, it means the target cannot be in the current column, so decrement `col` by 1 (move left).
7
Step 7: If `current < target`, it means the target cannot be in the current row, so increment `row` by 1 (move down).
8
Step 8: 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(m+n)

💾

Space Complexity

O(1)

💪 Constant space - Uses same memory regardless of input!

📝

Why?

The time complexity is O(m+n) because, in the worst case, we might traverse an entire row (n steps) and an entire column (m steps). The space complexity is O(1) because we are only using a constant amount of extra space for variables like `row`, `col`, and `current`, regardless of the size of the input matrix.

📖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

Binary Search on Each Row

Perform a binary search on each row of the matrix to find the target.

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

Trade-offs: This approach is simpler to implement but less efficient than the O(m+n) approach if m is significantly larger than log n.

Divide and Conquer

Recursively divide the matrix into smaller submatrices and search for the target within each submatrix.

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

Trade-offs: This approach can be more complex to implement and might not be as efficient as the O(m+n) approach in practice due to overhead of recursion.

✨

Key Insights

1Insight 1: The sorted nature of rows and columns allows for an efficient search strategy, avoiding a naive O(m*n) traversal.
2Insight 2: Starting the search from the top-right corner or bottom-left corner allows for eliminating either a row or a column in each comparison.
3Insight 3: The problem can be viewed as a modified binary search. Instead of bisecting a single array, we are effectively bisecting the search space in two dimensions by either moving to the next row or the previous column

📚

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 (either `matrix` is `null` or `matrix.length == 0` or `matrix[0].length == 0`). The solution explicitly checks for this and returns `false` immediately.
Edge case 2: Target smaller than the smallest element or larger than the largest element. The algorithm correctly handles this by either moving out of bounds (returning `false`) or finding the target within the loop.
Edge case 3: Target present multiple times. The algorithm will return `true` after finding the first occurrence.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Starting the search from the top-left corner or bottom-right corner. Starting from these corners does not allow you to eliminate either a row or a column effectively in each step, leading to a potentially inefficient algorithm.

✗Common mistake 2: Incorrectly implementing the movement logic (incrementing `col` instead of decrementing when the current element is greater than the target, or vice versa). This will lead to an infinite loop or incorrect results.

✗Common mistake 3: Not handling the edge case of an empty matrix.

✅

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 a specific value in a sorted database table where rows and columns represent different sorted attributes.

🏦Real-world scenario 2: In image processing, finding a specific pixel intensity in a sorted intensity map.

💡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

Medium problems are the bread and butter of technical interviews. Practice explaining your approach before coding.

⚠️ Watch Out

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

👨‍💻 From Experience

This problem pattern appears frequently in real codebases. I've used similar logic when building production systems.

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: July 31, 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

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

@DevExpert92Jul 14

The key insight here is recognizing the pattern. Once you see it, the solution becomes straightforward.

@AlgoMasterJul 7

❓

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 II"?

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?