240. Search a 2D Matrix II - Detailed Explanation

Free Coding Questions Catalog

Boost your coding skills with our essential coding questions catalog. Take a step towards a better tech career now!

Problem Statement

Description:
You are given an m x n matrix where each row is sorted in ascending order from left to right and each column is sorted in ascending order from top to bottom. Given an integer target, return true if the target is in the matrix or false otherwise.

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
Explanation:
The target 5 exists in the matrix.

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, 26, 30]
]
target = 20

Output: false
Explanation:
The target 20 does not exist in the matrix.

Constraints:

m == matrix.length
n == matrix[i].length
1 ≤ m, n ≤ 300
-10⁹ ≤ matrix[i][j] ≤ 10⁹
All integers in each row are sorted in ascending order.
All integers in each column are sorted in ascending order.
-10⁹ ≤ target ≤ 10⁹

Hints to Approach the Problem

Hint 1:
Notice that the rows and columns are sorted. This ordering means that you can eliminate an entire row or column based on a comparison with the target.
Hint 2:
A common strategy is to start at the top right or bottom left corner. From these positions, you have the advantage of making a decision: if the current number is greater than the target, you can move left (or up); if it is less than the target, you can move down (or right).
Hint 3:
Think about how each step reduces the search space. This “staircase search” ensures that you check at most m + n elements, making the approach efficient.

Approaches

Approach 1: Brute Force

Idea:
Check every element in the matrix and see if it equals the target.
Drawbacks:
This approach takes O(m * n) time, which can be inefficient if the matrix is large.

Approach 2: Staircase Search (Optimal)

Idea:
Start from the top right corner of the matrix.
- If the current element equals the target: Return true.
- If the current element is greater than the target: Move left, because all elements below in that column are even larger.
- If the current element is less than the target: Move down, because all elements to the left in that row are smaller.
Benefits:
Each step eliminates a row or a column, so the worst-case time complexity is O(m + n).

Code Implementations

Python Code

Python3

. . . .

Java Code

Java

. . . .

Complexity Analysis

Time Complexity:
In the worst-case scenario, you either move left through all columns or down through all rows, so the time complexity is O(m + n), where m is the number of rows and n is the number of columns.
Space Complexity:
The algorithm uses only a few variables for the indices and current element, so the space complexity is O(1).

Step-by-Step Walkthrough

Initialization:
- Start at the top right corner of the matrix, with row = 0 and col = n - 1.
Traversal:
- Compare the current element matrix[row][col] with the target:
  - Equal: Return true.
  - Greater: Move left (decrement col) because all elements below in that column are even larger.
  - Less: Move down (increment row) because all elements to the left are smaller.
Loop Termination:
- Continue the process until you either find the target or the indices go out of bounds (i.e., row becomes equal to m or col becomes less than 0).
Result:
- If the target is not found by the time you exit the loop, return false.

Visual Example

Consider the following matrix and target:

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

Step 1: Start at position (0, 4) with value 15.
Since 15 > 5, move left to position (0, 3).
Step 2: At position (0, 3) with value 11.
Since 11 > 5, move left to position (0, 2).
Step 3: At position (0, 2) with value 7.
Since 7 > 5, move left to position (0, 1).
Step 4: At position (0, 1) with value 4.
Since 4 < 5, move down to position (1, 1).
Step 5: At position (1, 1) with value 5.
The target is found, so return true.

Common Mistakes

Starting at the Wrong Corner:
Beginning at the bottom-right or top-left may not allow for efficient elimination of rows or columns.
Not Handling Boundaries:
Ensure that your loop correctly handles when the indices move out of the matrix bounds.
Assuming Matrix is Square:
The matrix might be rectangular; make sure to use m and n separately.

Edge Cases

Empty Matrix:
Return false if the matrix is empty or has no columns.
Single Element Matrix:
Check if the only element matches the target.
Target Outside Matrix Range:
If the target is smaller than the smallest element or larger than the largest element in the matrix, the answer is false.

Search a 2D Matrix I:
A similar problem where the entire matrix is sorted as if it were a flattened sorted array.
Find a Peak Element in a 2D Grid:
Another matrix search problem that involves different constraints.

Search a 2D Matrix I
Find a Peak Element
Number of Islands
Matrix Median