Search a 2D Matrix

LeetCode 74 | Difficulty: Medium

Medium

Problem Description

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.

Example 1:

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true

Example 2:

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Output: false

Constraints:

- `m == matrix.length`

- `n == matrix[i].length`

- `1 <= m, n <= 100`

- `-10^4 <= matrix[i][j], target <= 10^4`

Topics: Array, Binary Search, Matrix

---

Approach

Binary Search

Binary search reduces the search space by half at each step. The key insight is identifying the monotonic property — what condition lets you decide to go left or right?

When to use

Sorted array, or searching for a value in a monotonic function/space.

Matrix

Treat the matrix as a 2D grid. Common techniques: directional arrays (dx, dy) for movement, BFS/DFS for connected regions, in-place marking for visited cells, boundary traversal for spiral patterns.

When to use

Grid traversal, island problems, path finding, rotating/transforming matrices.

---

Solutions

Solution 1: C# (Best: 132 ms)

Metric	Value
Runtime	132 ms
Memory	N/A
Date	2018-04-02

Solution

public class Solution {
    public bool SearchMatrix(int[,] matrix, int target) {
      int m = matrix.GetLength(0), n = matrix.GetLength(1);
    int i=0, j= n-1;
    while (i<m && j >=0)
    {
        if (matrix[i, j] == target)
        {
            return true;
        }
        else if (target < matrix[i, j])
        {
            j--;
        }
        else
        {
            i++;
        }
    }
    return false;
    }
}

📜 1 more C# submission(s)

Submission (2018-03-31) — 224 ms, N/A

public class Solution {
    public bool SearchMatrix(int[,] matrix, int target) {
        int i=0, j=0, m = matrix.GetLength(0), n=matrix.GetLength(1);
    while(i<m && j<n)
    {
        if(matrix[i,j]>target)
        {
            return false;
        }
        else if(matrix[i,j]==target)
        {
            return true;
        }
        else if(target<=matrix[i,n-1])
        {
            j++;
        }
        else
        {
            i++;
        }
    }
    return false;
    }
}

---

Complexity Analysis

Approach	Time	Space
Binary Search	$O(log n)$	$O(1)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• Precisely define what the left and right boundaries represent, and the loop invariant.