Search a 2D Matrix II (Staircase)

📋

Problem

Imagine you are searching for a book in a library where shelves are sorted both by author and title. How do you quickly find if a book exists without scanning every shelf?

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, write an efficient algorithm to determine if a given target integer exists in the matrix. Return true if the target is found, otherwise false.

m == matrix.lengthn == matrix[i].length1 ≤ m, n ≤ 300-10^9 ≤ matrix[i][j], target ≤ 10^9

Edge cases: Empty matrix → falseSingle element matrix where element equals target → trueSingle element matrix where element does not equal target → false

</>

IDE

def searchMatrix(matrix: list[list[int]], target: int) -> bool:public boolean searchMatrix(int[][] matrix, int target)bool searchMatrix(vector<vector<int>>& matrix, int target)function searchMatrix(matrix, target)

def searchMatrix(matrix, target):
    # Write your solution here
    pass

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        // Write your solution here
        return false;
    }
}

#include <vector>
using namespace std;

bool searchMatrix(vector<vector<int>>& matrix, int target) {
    // Write your solution here
    return false;
}

function searchMatrix(matrix, target) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: falseIncorrect traversal logic missing the target when it exists.✅ Ensure to move left when current element > target and down when current element < target.

Wrong: trueReturning true without verifying matrix is non-empty or target presence.✅ Add checks for empty matrix or empty rows before searching.

Wrong: trueNot handling target smaller than smallest or larger than largest element, causing false positives.✅ Add early boundary checks comparing target with matrix[0][0] and matrix[m-1][n-1].

Wrong: falseSkipping duplicates or off-by-one errors causing missed targets in matrices with repeated rows.✅ Correctly update indices without skipping duplicates; verify loop conditions.

Wrong: TLEUsing brute force O(m*n) approach on large inputs.✅ Implement staircase search with O(m+n) complexity starting from top-right corner.

✓

Test Cases

Focus on handling empty and minimal input cases correctly.

Add boundary checks for target outside matrix range and test duplicates carefully.

Optimize your solution to avoid brute force and achieve O(m+n) time.

t1_01basic

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}

Expectedtrue

⏱ Performance - must finish in 2000ms

5 is present in the matrix at position (1,1).

💡 Start searching from the top-right corner of the matrix.

💡 If current element is greater than target, move left; if smaller, move down.

💡 Continue until you find the target or go out of bounds.

Why it failed: Failed to find target 5 in matrix; likely incorrect traversal logic or boundary checks. Fix by correctly moving left when current > target and down when current < target.

✓ Correctly found target 5 using staircase search.

t1_02basic

Input{"matrix":[[1,3,5,7],[10,11,16,20],[23,30,34,50]],"target":3}

Expectedtrue

⏱ Performance - must finish in 2000ms

3 is present in the matrix at position (0,1).

💡 Use the same top-right corner search strategy.

💡 Check if current element equals target; if not, decide direction based on comparison.

💡 Ensure to handle rows and columns correctly to avoid index errors.

Why it failed: Returned false despite target 3 being present; likely off-by-one error or incorrect movement direction. Fix by verifying index updates and comparison conditions.

✓ Correctly located target 3 in the matrix.

t2_01edge

Input{"matrix":[],"target":1}

Expectedfalse

⏱ Performance - must finish in 2000ms

Empty matrix contains no elements, so target cannot be found.

💡 Check if the matrix is empty before searching.

💡 Return false immediately if matrix or first row is empty.

💡 Avoid index errors by validating input size.

Why it failed: Code crashes or returns true on empty matrix input; fix by adding a check for empty matrix or empty rows before search.

✓ Correctly handled empty matrix by returning false.

t2_02edge

Input{"matrix":[[7]],"target":7}

Expectedtrue

⏱ Performance - must finish in 2000ms

Single element matrix where element equals target should return true.

💡 Handle single element matrices as a base case.

💡 Check if the only element equals the target.

💡 Return true if matched, false otherwise.

Why it failed: Returned false for single element matrix where element equals target; fix by adding base case or correct comparison for single element.

✓ Correctly found target in single element matrix.

t2_03edge

Input{"matrix":[[7]],"target":10}

Expectedfalse

⏱ Performance - must finish in 2000ms

Single element matrix where element does not equal target should return false.

💡 Check single element and compare with target.

💡 Return false if they do not match.

💡 Avoid unnecessary loops for single element.

Why it failed: Returned true incorrectly for single element matrix where element != target; fix by ensuring equality check is exact.

✓ Correctly returned false for single element matrix without target.

t3_01corner

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":0}

Expectedfalse

⏱ Performance - must finish in 2000ms

Target smaller than smallest element in matrix should return false.

💡 Check if target is less than the smallest element in matrix (top-left).

💡 If yes, return false immediately.

💡 Avoid unnecessary search when target is out of range.

Why it failed: Returned true or searched unnecessarily when target < smallest element; fix by adding early boundary check comparing target with matrix[0][0].

✓ Correctly returned false for target smaller than smallest element.

t3_02corner

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":31}

Expectedfalse

⏱ Performance - must finish in 2000ms

Target larger than largest element in matrix should return false.

💡 Check if target is greater than the largest element in matrix (bottom-right).

💡 If yes, return false immediately.

💡 Avoid unnecessary search when target is out of range.

Why it failed: Returned true or searched unnecessarily when target > largest element; fix by adding early boundary check comparing target with matrix[m-1][n-1].

✓ Correctly returned false for target larger than largest element.

t3_03corner

Input{"matrix":[[1,2,3],[1,2,3],[1,2,3]],"target":2}

Expectedtrue

⏱ Performance - must finish in 2000ms

Matrix with all rows identical tests correct traversal without skipping duplicates.

💡 Ensure search does not skip rows or columns with duplicate values.

💡 Check movement logic carefully when current equals target or when duplicates exist.

💡 Verify that search covers all possible positions.

Why it failed: Returned false due to skipping duplicates or incorrect movement; fix by correctly updating row and column indices without skipping duplicates.

✓ Correctly found target in matrix with identical rows.

t4_01performance

Input{"_description":"n=300 at constraint boundary - executor generates this"}

Expectednull

⏱ Performance - must finish in 2000ms

Matrix size m=n=300, O(m+n) = O(600) must complete in 2s.

💡 Use staircase search starting from top-right corner for O(m+n) time.

💡 Avoid brute force O(m*n) which is too slow for large inputs.

💡 Optimize boundary checks and loop conditions.

Why it failed: TLE due to using brute force O(m*n) approach; fix by implementing staircase search with O(m+n) complexity.

✓ Algorithm runs within time limit using O(m+n) staircase search.

Practice

1. You need to ship packages within a given number of days. Each package has a weight, and you must ship packages in order without splitting any package. You want to find the minimum ship capacity to ship all packages within the deadline. Which algorithmic approach guarantees finding the optimal ship capacity efficiently?

easy

A. Greedy approach that assigns packages to days until capacity is reached, then moves to next day without binary search

B. Dynamic programming to find the minimum capacity by exploring all subsets of packages and days

C. Sorting packages and using a two-pointer technique to assign packages to days

D. Binary search on the answer space (capacity) combined with a feasibility check to verify if shipping within days is possible

Solution

1. Step 1: Understand the problem constraints

   The problem requires finding a minimum capacity that allows shipping all packages in order within a fixed number of days.

2. Step 2: Recognize the pattern

   Binary searching the capacity (answer space) and checking feasibility is the optimal approach because capacity ranges between max package weight and sum of all weights, and feasibility can be checked in linear time.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Binary search on answer space is classic for optimization with feasibility checks [OK]

Hint: Binary search on capacity range solves this optimally [OK]

Common Mistakes:

• Thinking greedy alone finds minimal capacity
• Confusing DP with subset sums
• Using two pointers without sorting relevance

2. The following code attempts to find the kth smallest element in a sorted matrix using a min-heap. Identify the line containing the subtle bug that can cause incorrect results when duplicates exist or when counting is off.

medium

A. Line where count is incremented after the kth check (count += 1)

B. Line where initial elements are pushed into the heap (heapq.heappush in for loop)

C. Line where the kth element is checked (if count == k: return val)

D. Line where next element in the row is pushed (heapq.heappush inside while loop)

Solution

1. Step 1: Understand counting logic

   Count should increment before checking if count == k to correctly identify the kth popped element.

2. Step 2: Identify off-by-one bug

   Currently, count is incremented after the check, so the function returns the (k-1)th element instead of kth.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Increment count before kth check fixes off-by-one error [OK]

Hint: Check order of count increment and kth check [OK]

Common Mistakes:

• Off-by-one in counting popped elements
• Returning before incrementing count
• Misplaced heap push causing missing elements

3. Consider the following buggy code snippet for checking if arrival is possible on time. Which line contains the subtle bug that can cause incorrect feasibility results?

from math import ceil

def can_arrive(dist, hour, speed):
    total_time = 0.0
    for i in range(len(dist)):
        total_time += ceil(dist[i] / speed)
    total_time -= ceil(dist[-1] / speed)  # Adjust last segment
    total_time += dist[-1] / speed
    return total_time <= hour

medium

A. Line 5: total_time += ceil(dist[i] / speed)

B. Line 6: total_time -= ceil(dist[-1] / speed) # Adjust last segment

C. Line 4: for i in range(len(dist))

D. Line 7: total_time += dist[-1] / speed

Solution

1. Step 1: Analyze loop bounds

   The loop iterates over all segments including the last, adding ceil for all, which overestimates time for last segment.

2. Step 2: Identify correct approach

   Only the first n-1 segments should use ceil; the last segment should add exact division time without ceiling.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Loop should be for i in range(len(dist) - 1) [OK]

Hint: Last segment time must not be ceiled [OK]

Common Mistakes:

• Applying ceil to last segment
• Incorrect loop range including last segment

4. What is the time complexity of the optimal solution that uses binary search on the answer space combined with prefix sums and binary search for feasibility checks in the Split Array Largest Sum problem?

medium

A. O(n log(sum(nums))) since binary search is done only on sums without extra binary searches

B. O(n^m) due to exploring all splits recursively

C. O(n^2 log(sum(nums))) because feasibility check scans all subarrays linearly

D. O(n log n log(sum(nums))) because each binary search iteration uses binary search on prefix sums

Solution

1. Step 1: Identify outer binary search on answer space

   Binary search on possible sums takes O(log(sum(nums))) iterations.

2. Step 2: Analyze feasibility check using binary search on prefix sums

   Each feasibility check uses binary search (O(log n)) for each subarray, repeated up to n times -> O(n log n).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Nested binary searches yield O(n log n log(sum(nums))) [OK]

Hint: Feasibility check uses binary search inside binary search [OK]

Common Mistakes:

• Assuming feasibility check is O(n) ignoring binary search
• Confusing n and m in complexity
• Ignoring log factor from binary search on sums

5. Suppose the problem is modified so that each number in the array can be divided multiple times (reuse allowed), and the sum of all ceiling divisions must still be ≤ threshold. Which modification to the algorithm is necessary to correctly find the smallest divisor?

hard

A. Use the same binary search with feasibility function, but modify feasibility to count repeated divisions per element

B. Switch to a greedy approach that picks divisors based on the largest elements first

C. Use dynamic programming to track all possible divisor sums with reuse

D. Binary search is no longer applicable; use brute force over all divisors

Solution

1. Step 1: Understand the reuse modification

   Allowing multiple divisions per element means feasibility must consider repeated divisions, but the divisor search space remains monotonic.

2. Step 2: Adapt feasibility function

   Modify feasibility to count how many times each element can be divided by the divisor (e.g., sum of ceiling divisions with reuse).

3. Step 3: Retain binary search on answer space

   Binary search still applies because the feasibility condition remains monotonic with divisor.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Binary search with adapted feasibility handles reuse -> [OK]

Hint: Reuse changes feasibility, not binary search applicability [OK]

Common Mistakes:

• Discarding binary search prematurely
• Using greedy which breaks global constraints
• Overcomplicating with DP when not needed