Search a 2D Matrix II

LeetCode 240 | Difficulty: Medium

Medium

Problem Description

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 from left to right.

- Integers in each column are sorted in ascending from top to bottom.

Example 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 = 5
Output: true

Example 2:

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
Output: false

Constraints:

- `m == matrix.length`

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

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

- `-10^9 <= matrix[i][j] <= 10^9`

- All the integers in each row are **sorted** in ascending order.

- All the integers in each column are **sorted** in ascending order.

- `-10^9 <= target <= 10^9`

Topics: Array, Binary Search, Divide and Conquer, 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: 228 ms)

Metric	Value
Runtime	228 ms
Memory	31.6 MB
Date	2020-01-03

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>=0 && i<m && j>=0 && j<n)
    {
        if(target==matrix[i,j]) return true;
        else if(target<matrix[i,j]) j--;
        else i++;
    }
    return false;
    }
}

📜 1 more C# submission(s)

Submission (2018-04-14) — 276 ms, N/A

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>=0 && i<m && j>=0 && j<n)
    {
        if(target==matrix[i,j]) return true;
        else if(target<matrix[i,j]) 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.