Search a 2D Matrix II - Practice Coding Problems

Search a 2D Matrix II - Problem

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 order from left to right.
• Integers in each column are sorted in ascending order from top to bottom.

Return true if target is found, otherwise return false.

Input & Output

Example 1 — Basic Search

$ Input: matrix = [[1,4,7,11],[2,5,8,12],[3,6,9,16]], target = 5

› Output: true

💡 Note: Target 5 exists in the matrix at position (1,1). Using the optimal approach: start at top-right (11), 11 > 5 so move left to 7, 7 > 5 so move left to 4, 4 < 5 so move down to 5, found!

Example 2 — Target Not Found

$ Input: matrix = [[1,4,7,11],[2,5,8,12],[3,6,9,16]], target = 13

› Output: false

💡 Note: Target 13 does not exist in the matrix. Starting from top-right, we would traverse through several cells but never find 13, eventually going out of bounds.

Example 3 — Single Element

$ Input: matrix = [[5]], target = 5

› Output: true

💡 Note: Edge case with single element matrix. The target 5 matches the only element in the matrix.

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input

Sorted matrix and target value to find

Strategy

Start from top-right, eliminate row or column

Output

Return true if target found, false otherwise

Key Takeaway

🎯 Key Insight: Start from top-right corner to eliminate either a row or column at each comparison step

Asked in

G Google 42 a Amazon 38 M Microsoft 28 A Apple 22

The key insight is to start from the top-right corner where we can eliminate either a row or column at each step. If current element is greater than target, move left; if smaller, move down. Best approach achieves O(m+n) time complexity using the sorted matrix property optimally.

Common Approaches

Approach	Time	Space	Notes
✓ Row-wise Binary Search	O(m×log n)	O(1)	Apply binary search on each row of the matrix
Brute Force	O(m×n)	O(1)	Check every element in the matrix one by one
Search Space Reduction	O(m+n)	O(1)	Start from top-right corner, eliminate rows or columns based on comparison

Row-wise Binary Search — Algorithm Steps

Step 1: Iterate through each row
Step 2: Apply binary search on current row
Step 3: Return true if target found in any row

Visualization

Tap to expand

Step-by-Step Walkthrough

Select Row

Choose next row to search

Binary Search

Apply binary search on selected row

Result

Return true if found in any row

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

bool binarySearch(int* arr, int size, int target) {
    int left = 0, right = size - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) {
            return true;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return false;
}

bool solution(int** matrix, int matrixSize, int* matrixColSize, int target) {
    if (matrixSize == 0 || matrixColSize[0] == 0) {
        return false;
    }
    
    for (int i = 0; i < matrixSize; i++) {
        if (binarySearch(matrix[i], matrixColSize[i], target)) {
            return true;
        }
    }
    return false;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    int target;
    scanf("%d", &target);
    
    // Simple parsing for demo - assumes well-formed input
    int matrix[100][100];
    int matrixSize = 0, matrixColSize[100];
    
    // Parse matrix manually (simplified)
    char* ptr = line + 1; // skip first '['
    while (*ptr && *ptr != ']') {
        if (*ptr == '[') {
            ptr++;
            int col = 0;
            while (*ptr && *ptr != ']') {
                if (*ptr >= '0' && *ptr <= '9' || *ptr == '-') {
                    matrix[matrixSize][col++] = strtol(ptr, &ptr, 10);
                } else {
                    ptr++;
                }
            }
            matrixColSize[matrixSize] = col;
            matrixSize++;
        }
        ptr++;
    }
    
    int* matrixRowPtr[100];
    for (int i = 0; i < matrixSize; i++) {
        matrixRowPtr[i] = matrix[i];
    }
    
    bool result = solution(matrixRowPtr, matrixSize, matrixColSize, target);
    printf(result ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m×log n)

Binary search on each of m rows takes O(log n) time

⚡ Linearithmic

Space Complexity

O(1)

Only use constant extra space for binary search variables

✓ Linear Space

125.0K Views

High Frequency

~15 min Avg. Time

2.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Row-wise Binary Search — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler