Search a 2D Matrix II (Staircase)

🎯

Search a 2D Matrix II (Staircase)

mediumBINARY_SEARCHAmazonGoogleMicrosoft

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?

💡 This problem involves searching in a 2D matrix where each row and column is sorted. Beginners often struggle because the matrix is not sorted in a simple linear way, so classic binary search on a 1D array doesn't directly apply. Understanding how to leverage the matrix's sorted properties is key.

📋

Problem Statement

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

💡

Example

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"

Outputtrue

5 is present in the matrix at position (1,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 = 20"

Outputfalse

20 is not present in the matrix.

• Empty matrix → false
• Single element matrix where element equals target → true
• Single element matrix where element does not equal target → false
• Target smaller than smallest element → false
• Target larger than largest element → false

⚠️

Common Mistakes

Starting from top-left or bottom-left corner instead of top-right

Algorithm fails to eliminate rows or columns correctly, leading to incorrect results or infinite loops

✅ Always start from top-right corner to leverage sorted properties correctly

Not checking for empty matrix or empty rows

Code throws runtime errors or exceptions

✅ Add checks for empty matrix or empty first row before processing

Using '==' instead of '>=' or '<=' incorrectly in comparisons

May skip valid elements or cause infinite loops

✅ Use strict comparisons and update pointers correctly based on comparison results

Confusing row and column indices when moving pointers

Moves in wrong direction, causing incorrect search or out-of-bounds errors

✅ Remember row increases move down, column decreases move left

Attempting binary search on columns without sorted columns

Binary search fails because columns are sorted but not independently searchable

✅ Use staircase search or binary search on rows only

🧠

Brute Force (Nested Loops)

💡 Starting with brute force helps understand the problem's nature by checking every element. Though inefficient, it guarantees correctness and builds intuition about the matrix layout.

Intuition

Check every element in the matrix one by one until the target is found or all elements are exhausted.

Algorithm

1. Iterate over each row in the matrix.
2. Within each row, iterate over each element.
3. Compare the current element with the target.
4. If found, return true; if all elements checked without a match, return false.

💡 This approach is straightforward but inefficient because it ignores the sorted property of the matrix.

</>

Code

def searchMatrix(matrix, target):
    for row in matrix:
        for num in row:
            if num == target:
                return True
    return False

# Driver code
if __name__ == '__main__':
    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
    print(searchMatrix(matrix, target))  # Expected: True

Line Notes

for row in matrix:Iterate over each row to access all elements because we need to check every element in the matrix.

for num in row:Iterate over each element in the current row to examine each number individually.

if num == target:Check if the current element matches the target to return early if found.

return TrueReturn immediately once target is found to avoid unnecessary checks and improve efficiency.

public class Solution {
    public static boolean searchMatrix(int[][] matrix, int target) {
        for (int[] row : matrix) {
            for (int num : row) {
                if (num == target) {
                    return true;
                }
            }
        }
        return false;
    }

    public static void main(String[] args) {
        int[][] 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}
        };
        int target = 5;
        System.out.println(searchMatrix(matrix, target)); // Expected: true
    }
}

Line Notes

for (int[] row : matrix)Loop through each row to access all elements in the matrix.

for (int num : row)Loop through each element in the current row to check each number.

if (num == target)Check if the current element equals the target to return early if found.

return trueReturn immediately when target is found to avoid unnecessary iterations.

#include <iostream>
#include <vector>
using namespace std;

bool searchMatrix(vector<vector<int>>& matrix, int target) {
    for (auto& row : matrix) {
        for (int num : row) {
            if (num == target) {
                return true;
            }
        }
    }
    return false;
}

int main() {
    vector<vector<int>> 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}
    };
    int target = 5;
    cout << (searchMatrix(matrix, target) ? "true" : "false") << endl; // Expected: true
    return 0;
}

Line Notes

for (auto& row : matrix)Range-based loop to iterate over each row to access all elements.

for (int num : row)Iterate over each element in the current row to check each number.

if (num == target)Check if the current element matches the target to return early if found.

return trueReturn immediately when target is found to avoid unnecessary checks.

function searchMatrix(matrix, target) {
    for (const row of matrix) {
        for (const num of row) {
            if (num === target) {
                return true;
            }
        }
    }
    return false;
}

// Test
const 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]
];
const target = 5;
console.log(searchMatrix(matrix, target)); // Expected: true

Line Notes

for (const row of matrix)Loop over each row to access all elements in the matrix.

for (const num of row)Loop over each element in the current row to check each number.

if (num === target)Check if the current element equals the target to return early if found.

return trueReturn immediately when target is found to avoid unnecessary iterations.

⏱

Complexity

TimeO(m*n)

SpaceO(1)

We check every element in the matrix once, so time complexity is proportional to total elements m*n. Space is constant as no extra data structures are used.

💡 For a 300x300 matrix, this means up to 90,000 checks, which is inefficient for large inputs.

Interview Verdict: Accepted but inefficient

This approach works but is too slow for large matrices. It is useful to understand the problem but not practical for interviews.

🧠

Staircase Search (Start from Top-Right Corner)

💡 This approach leverages the sorted properties of rows and columns to eliminate rows or columns in each step, improving efficiency drastically.

Intuition

Start from the top-right corner. If the current element is greater than target, move left to smaller elements; if smaller, move down to larger elements. Repeat until found or out of bounds.

Algorithm

1. Initialize row = 0 and col = number_of_columns - 1 (top-right corner).
2. While row is within matrix height and col is non-negative:
3. Compare matrix[row][col] with target.
4. If equal, return true; if matrix[row][col] > target, move left (col--); else move down (row++).
5. If loop ends without finding target, return false.

💡 This algorithm cleverly reduces search space by one row or column each iteration, making it efficient and easy to implement.

</>

Code

def searchMatrix(matrix, target):
    if not matrix or not matrix[0]:
        return False
    row, col = 0, len(matrix[0]) - 1
    while row < len(matrix) and col >= 0:
        if matrix[row][col] == target:
            return True
        elif matrix[row][col] > target:
            col -= 1
        else:
            row += 1
    return False

# Driver code
if __name__ == '__main__':
    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
    print(searchMatrix(matrix, target))  # Expected: True

Line Notes

if not matrix or not matrix[0]:Check for empty matrix to avoid errors and handle edge cases gracefully.

row, col = 0, len(matrix[0]) - 1Start at top-right corner to leverage sorted properties and eliminate search space efficiently.

while row < len(matrix) and col >= 0:Traverse while indices are valid to stay within matrix bounds.

if matrix[row][col] == target:Return immediately if target found to stop searching early.

public class Solution {
    public static boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return false;
        int row = 0, col = matrix[0].length - 1;
        while (row < matrix.length && col >= 0) {
            if (matrix[row][col] == target) return true;
            else if (matrix[row][col] > target) col--;
            else row++;
        }
        return false;
    }

    public static void main(String[] args) {
        int[][] 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}
        };
        int target = 5;
        System.out.println(searchMatrix(matrix, target)); // Expected: true
    }
}

Line Notes

if (matrix == null || matrix.length == 0 || matrix[0].length == 0)Check for empty matrix to prevent exceptions and handle edge cases.

int row = 0, col = matrix[0].length - 1;Initialize pointers at top-right corner to use matrix's sorted properties.

while (row < matrix.length && col >= 0)Traverse while indices are valid to stay within matrix bounds.

if (matrix[row][col] == target) return true;Return immediately if target found to stop searching early.

#include <iostream>
#include <vector>
using namespace std;

bool searchMatrix(vector<vector<int>>& matrix, int target) {
    if (matrix.empty() || matrix[0].empty()) return false;
    int row = 0, col = matrix[0].size() - 1;
    while (row < (int)matrix.size() && col >= 0) {
        if (matrix[row][col] == target) return true;
        else if (matrix[row][col] > target) col--;
        else row++;
    }
    return false;
}

int main() {
    vector<vector<int>> 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}
    };
    int target = 5;
    cout << (searchMatrix(matrix, target) ? "true" : "false") << endl; // Expected: true
    return 0;
}

Line Notes

if (matrix.empty() || matrix[0].empty()) return false;Check for empty matrix to avoid runtime errors and handle edge cases.

int row = 0, col = matrix[0].size() - 1;Start at top-right corner for efficient search leveraging sorted properties.

while (row < (int)matrix.size() && col >= 0)Traverse while indices are valid to stay within matrix bounds.

if (matrix[row][col] == target) return true;Return immediately if target found to stop searching early.

function searchMatrix(matrix, target) {
    if (!matrix.length || !matrix[0].length) return false;
    let row = 0, col = matrix[0].length - 1;
    while (row < matrix.length && col >= 0) {
        if (matrix[row][col] === target) return true;
        else if (matrix[row][col] > target) col--;
        else row++;
    }
    return false;
}

// Test
const 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]
];
const target = 5;
console.log(searchMatrix(matrix, target)); // Expected: true

Line Notes

if (!matrix.length || !matrix[0].length) return false;Check for empty matrix to prevent errors and handle edge cases.

let row = 0, col = matrix[0].length - 1;Initialize pointers at top-right corner to leverage sorted properties.

while (row < matrix.length && col >= 0)Traverse while indices are valid to stay within matrix bounds.

if (matrix[row][col] === target) return true;Return immediately if target found to stop searching early.

⏱

Complexity

TimeO(m + n)

SpaceO(1)

Each step moves either left or down, so at most m + n steps are taken. No extra space is used.

💡 For a 300x300 matrix, this means at most 600 steps, which is very efficient compared to checking every element.

Interview Verdict: Accepted and optimal for this problem

This approach is the best balance of simplicity and efficiency, ideal for interviews.

🧠

Binary Search on Each Row

💡 This approach applies binary search on each row individually, leveraging the sorted rows but ignoring column sorting, improving over brute force but less efficient than staircase search.

Intuition

Since each row is sorted, perform binary search on each row to find the target. If found in any row, return true.

Algorithm

1. For each row in the matrix:
2. Perform binary search to find the target in that row.
3. If found, return true.
4. If all rows searched without success, return false.

💡 This approach improves search within rows but still requires scanning all rows, so it is not fully optimal.

</>

Code

def binary_search(row, target):
    left, right = 0, len(row) - 1
    while left <= right:
        mid = (left + right) // 2
        if row[mid] == target:
            return True
        elif row[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return False

def searchMatrix(matrix, target):
    for row in matrix:
        if binary_search(row, target):
            return True
    return False

# Driver code
if __name__ == '__main__':
    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
    print(searchMatrix(matrix, target))  # Expected: True

Line Notes

left, right = 0, len(row) - 1Initialize binary search pointers for the current row to define search boundaries.

mid = (left + right) // 2Calculate middle index to check the middle element efficiently.

if row[mid] == target:Return true immediately if target found to stop searching this row.

for row in matrix:Iterate over each row to apply binary search individually.

public class Solution {
    private static boolean binarySearch(int[] row, int target) {
        int left = 0, right = row.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (row[mid] == target) return true;
            else if (row[mid] < target) left = mid + 1;
            else right = mid - 1;
        }
        return false;
    }

    public static boolean searchMatrix(int[][] matrix, int target) {
        for (int[] row : matrix) {
            if (binarySearch(row, target)) return true;
        }
        return false;
    }

    public static void main(String[] args) {
        int[][] 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}
        };
        int target = 5;
        System.out.println(searchMatrix(matrix, target)); // Expected: true
    }
}

Line Notes

int left = 0, right = row.length - 1;Initialize binary search pointers to define the search range in the row.

int mid = left + (right - left) / 2;Calculate mid index safely to avoid overflow.

if (row[mid] == target) return true;Return true immediately if target found to stop searching this row.

for (int[] row : matrix)Iterate over each row to apply binary search individually.

#include <iostream>
#include <vector>
using namespace std;

bool binarySearch(const vector<int>& row, int target) {
    int left = 0, right = (int)row.size() - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (row[mid] == target) return true;
        else if (row[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return false;
}

bool searchMatrix(vector<vector<int>>& matrix, int target) {
    for (const auto& row : matrix) {
        if (binarySearch(row, target)) return true;
    }
    return false;
}

int main() {
    vector<vector<int>> 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}
    };
    int target = 5;
    cout << (searchMatrix(matrix, target) ? "true" : "false") << endl; // Expected: true
    return 0;
}

Line Notes

int left = 0, right = (int)row.size() - 1;Initialize binary search pointers to define the search range in the row.

int mid = left + (right - left) / 2;Calculate mid index safely to avoid overflow.

if (row[mid] == target) return true;Return true immediately if target found to stop searching this row.

for (const auto& row : matrix)Iterate over each row to apply binary search individually.

function binarySearch(row, target) {
    let left = 0, right = row.length - 1;
    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        if (row[mid] === target) return true;
        else if (row[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return false;
}

function searchMatrix(matrix, target) {
    for (const row of matrix) {
        if (binarySearch(row, target)) return true;
    }
    return false;
}

// Test
const 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]
];
const target = 5;
console.log(searchMatrix(matrix, target)); // Expected: true

Line Notes

let left = 0, right = row.length - 1;Initialize binary search pointers to define the search range in the row.

let mid = Math.floor((left + right) / 2);Calculate mid index to check the middle element efficiently.

if (row[mid] === target) return true;Return true immediately if target found to stop searching this row.

for (const row of matrix)Iterate over each row to apply binary search individually.

⏱

Complexity

TimeO(m * log n)

SpaceO(1)

Binary search on each of the m rows takes O(log n) time, so total is O(m log n). Space is constant.

💡 For a 300x300 matrix, this means about 300 * 9 = 2700 operations, which is efficient but slower than staircase search.

Interview Verdict: Accepted but not optimal

This approach is a good improvement over brute force but not the best. Interviewers expect the staircase search for optimality.

📊

All Approaches - One-Glance Tradeoffs

💡 The staircase search is the best approach to implement in 95% of interviews due to its optimal time and simplicity.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(m*n)	O(1)	No	N/A	Mention only - never code
2. Staircase Search (Top-Right Corner)	O(m + n)	O(1)	No	N/A	Code this approach
3. Binary Search on Each Row	O(m log n)	O(1)	No	N/A	Mention as intermediate improvement

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding each approach, and prepare to explain tradeoffs clearly in interviews.

How to Present

Step 1: Clarify the problem constraints and input format.Step 2: Describe the brute force approach to show understanding.Step 3: Explain the staircase search as the optimal solution leveraging matrix properties.Step 4: Optionally mention binary search on rows as an intermediate approach.Step 5: Code the staircase search solution carefully.Step 6: Test with edge cases and explain complexity.

Time Allocation

Clarify: 3min → Approach: 5min → Code: 10min → Test: 5min. Total ~23min

What the Interviewer Tests

The interviewer tests your ability to leverage sorted matrix properties, optimize search, and write clean, bug-free code.

Common Follow-ups

• What if the matrix is not sorted by columns? → Staircase search won't work; brute force or other methods needed.
• Can you search for multiple targets efficiently? → Preprocessing or indexing might help.

💡 These follow-ups test your understanding of assumptions and ability to adapt solutions.

🔍

Pattern Recognition

When to Use

1) Matrix rows and columns sorted ascending, 2) Need to find target efficiently, 3) Matrix not flattened, 4) Can move in two directions to eliminate search space

Signature Phrases

each row is sortedeach column is sortedsearch target in matrix

NOT This Pattern When

Problems where matrix is unsorted or only rows or columns sorted but not both, requiring different approaches.

Similar Problems

Search a 2D Matrix I - simpler because matrix is sorted row-wise and column-wise as a flattened arrayFind Peak Element - binary search on arraysKth Smallest Element in a Sorted Matrix - uses matrix properties for search

Practice

1. Given the following recursive binary search code, what is the return value when searching for target = 3 in nums = [1, 3, 5] starting with low=0 and high=2?

def binary_search_recursive(nums, target, low, high):
    if low > high:
        return -1
    mid = low + (high - low) // 2
    if nums[mid] == target:
        return mid
    elif nums[mid] < target:
        return binary_search_recursive(nums, target, mid + 1, high)
    else:
        return binary_search_recursive(nums, target, low, mid - 1)

print(binary_search_recursive([1,3,5], 3, 0, 2))

easy

A. -1

B. 1

C. 0

D. 2

Solution

1. Step 1: Calculate mid for low=0, high=2

   mid = 0 + (2-0)//2 = 1; nums[1] = 3 equals target -> return 1.

2. Final Answer:

   Option B -> Option B

3. Quick Check:

   Target found at index 1 on first recursion [OK]

Hint: Mid calculation picks index 1 with target 3 [OK]

Common Mistakes:

• Returning -1 if confused about base case
• Off-by-one errors in mid calculation
• Returning wrong index due to boundary errors

2. Consider the following Python code implementing the min-heap approach to find the kth smallest element in a sorted matrix. Given the matrix [[1,3],[2,4]] and k = 3, what value does the function return?

easy

A. 2

B. 4

C. 3

D. 1

Solution

1. Step 1: Initialize min-heap with first elements

   Push (1,0,0) and (2,1,0) into heap.

2. Step 2: Extract elements until count == k

   Pop 1 (count=1), push 3 from row 0; pop 2 (count=2), push 4 from row 1; pop 3 (count=3), return 3.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Third smallest element is 3 [OK]

Hint: Trace heap pops and pushes carefully [OK]

Common Mistakes:

• Off-by-one counting of popped elements
• Returning wrong popped value
• Confusing row and column indices

3. Given the following code for searching a target in a rotated sorted array, what is the return value of search([3,4,1,2], 1)?

easy

A. -1

B. 1

C. 2

D. 3

Solution

1. Step 1: Trace find_pivot on [3,4,1,2]

   low=0, high=3; mid=1; nums[mid]=4 > nums[high]=2 -> low=mid+1=2; now low=2, high=3; mid=2; nums[mid]=1 <= nums[high]=2 -> high=mid=2; loop ends, pivot=2.

2. Step 2: Determine which half to search

   nums[pivot]=1 ≤ target=1 ≤ nums[-1]=2 -> search right half: binary_search(nums, 2, 3, 1).

3. Step 3: Binary search for target=1 between indices 2 and 3

   mid=2; nums[2]=1 == target -> return 2.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Pivot found at index 2, target found at index 2 [OK]

Hint: Pivot index guides binary search range [OK]

Common Mistakes:

• Off-by-one errors in binary search boundaries
• Confusing pivot index with target index

4. What is the time complexity of the min-heap based approach to find the kth smallest element in an n x n sorted matrix, where k ≤ n²? Assume the heap operations take O(log n) time.

medium

A. O(k log n)

B. O(k log k)

C. O(n log k)

D. O(n^2 log n)

Solution

1. Step 1: Analyze heap size and operations

   The heap holds at most n elements (one from each row), so heap operations cost O(log n).

2. Step 2: Count total heap operations

   We pop and push at most k times, so total time is O(k log n).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Heap size bounded by n, operations proportional to k [OK]

Hint: Heap size limited to n, not k or n² [OK]

Common Mistakes:

• Assuming heap size grows to k or n²
• Confusing k and n in log factors
• Thinking complexity is O(n^2 log n)

5. Identify the bug in the following modified code snippet for the Minimum Days to Make m Bouquets problem:

medium

A. The feasibility function does not reset flowers count correctly.

B. Binary search boundaries are incorrectly set from 0 instead of min bloom day.

C. The initial check for m * k > n is missing, causing unnecessary computation.

D. Early stopping in feasibility function is missing, causing slower runtime.

Solution

1. Step 1: Check initial conditions

   The code lacks the check if m * k > n, which means it's impossible to make required bouquets.

2. Step 2: Consequences of missing check

   Without this, the code runs unnecessary binary search and feasibility checks, possibly returning wrong answers or timing out.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Adding the initial impossible case check fixes the bug. [OK]

Hint: Always check if total flowers suffice before processing [OK]

Common Mistakes:

• Forgetting impossible case check
• Misresetting flowers count in feasibility