Search a 2D Matrix - Practice Coding Problems

Search a 2D Matrix - Problem

You are given an m x n integer matrix matrix with the following two properties:

Each row is sorted in non-decreasing order.
The first integer of each row is greater than the last integer of the previous row.

Given an integer target, return true if target is in matrix or false otherwise.

You must write a solution in O(log(m * n)) time complexity.

Input & Output

Example 1 — Basic Search

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

› Output: true

💡 Note: The target 5 exists in the matrix at position [1,1]. The matrix satisfies both properties: rows are sorted and first element of each row is greater than last element of previous row.

Example 2 — Target Not Found

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

› Output: true

💡 Note: The target 13 exists in the matrix at position [3,1]. Even though it's in the last row, binary search efficiently finds it in O(log(m*n)) time.

Example 3 — Target Not Present

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

› Output: false

💡 Note: The target 15 does not exist anywhere in the matrix. Binary search efficiently determines this without checking all elements.

Constraints

m == matrix.length
n == matrix[i].length
1 ≤ m, n ≤ 100
-10⁴ ≤ matrix[i][j], target ≤ 10⁴

Visualization

Tap to expand

Understanding the Visualization

Input

Sorted matrix with special properties + target value

Process

Use binary search treating matrix as 1D array

Output

Return true if target found, false otherwise

Key Takeaway

🎯 Key Insight: A sorted matrix with special properties can be searched like a single sorted array using coordinate transformation

Asked in

G Google 45 a Amazon 38 M Microsoft 32 Apple 25

The key insight is that a sorted matrix with the given properties can be treated as a single sorted 1D array. The optimal approach uses binary search by mapping 2D coordinates to 1D indices: row = mid / n and col = mid % n. Time: O(log(m*n)), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Search Row Then Column	O(log m + log n)	O(1)	First find the correct row using binary search, then search within that row
Binary Search (Treat as 1D Array)	O(log(m*n))	O(1)	Convert 2D coordinates to 1D index and use binary search
Linear Search	O(m*n)	O(1)	Check every element in the matrix one by one

Search Row Then Column — Algorithm Steps

Step 1: Binary search to find the correct row
Step 2: Check if target could be in this row
Step 3: Binary search within the found row

Visualization

Tap to expand

Step-by-Step Walkthrough

Find Row

Binary search to find row containing target

Search Row

Binary search within the found row

Result

Return true if found, false otherwise

Code -

solution.c — C

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

bool solution(int matrix[][100], int rows, int cols, int target) {
    if (rows == 0 || cols == 0) return false;
    
    // Find the correct row
    int top = 0, bottom = rows - 1;
    while (top <= bottom) {
        int mid = (top + bottom) / 2;
        if (matrix[mid][0] <= target && target <= matrix[mid][cols-1]) {
            // Search in this row
            int left = 0, right = cols - 1;
            while (left <= right) {
                int colMid = (left + right) / 2;
                if (matrix[mid][colMid] == target) {
                    return true;
                } else if (matrix[mid][colMid] < target) {
                    left = colMid + 1;
                } else {
                    right = colMid - 1;
                }
            }
            return false;
        } else if (matrix[mid][0] > target) {
            bottom = mid - 1;
        } else {
            top = mid + 1;
        }
    }
    
    return false;
}

int main() {
    int matrix[100][100];
    int rows = 0, cols = 0;
    char line[1000];
    
    fgets(line, sizeof(line), stdin);
    
    // Simple matrix parsing
    char* ptr = line + 1;
    while (*ptr && *ptr != ']' || *(ptr+1) != ']') {
        if (*ptr == '[') {
            ptr++;
            cols = 0;
            char* start = ptr;
            while (*ptr && *ptr != ']') {
                if (*ptr == ',' || *ptr == ']') {
                    char temp = *ptr;
                    *ptr = '\0';
                    matrix[rows][cols] = atoi(start);
                    cols++;
                    *ptr = temp;
                    if (*ptr == ',') {
                        ptr++;
                        start = ptr;
                    }
                } else {
                    ptr++;
                }
            }
            if (*ptr == ']') {
                char temp = *ptr;
                *ptr = '\0';
                matrix[rows][cols] = atoi(start);
                cols++;
                *ptr = temp;
                ptr++;
            }
            rows++;
        } else {
            ptr++;
        }
    }
    
    int target;
    scanf("%d", &target);
    
    bool result = solution(matrix, rows, cols, target);
    printf(result ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(log m + log n)

Binary search on rows O(log m) + binary search within row O(log n)

⚡ Linearithmic

Space Complexity

O(1)

Only using constant extra space for variables

✓ Linear Space

67.5K Views

High Frequency

~15 min Avg. Time

1.9K 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

Search Row Then Column — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler