Find a Value in a Matrix With Sorted Rows and Columns

Medium15–20 min

Topics

ArrayMatrixBinary Search

Companies

AmazonMicrosoftGoogleAdobe

You're given an m × n matrix where every row is sorted ascending left to right, and every column is sorted ascending top to bottom — but unlike the simpler matrix search, it does not flatten into one sorted sequence. Given an integer target, return whether it exists anywhere in the matrix. Solve it in O(m + n) time using a staircase search that starts at the top-right corner and, on each comparison, eliminates an entire row or an entire column.

Test Case 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

Explanation:5 sits at matrix[1][1].

Test Case 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

Explanation:20 falls between 19 and 21, but never appears.

Test Case 3:

Input:matrix = [[1]], target = 1

Output:true

Explanation:A single-cell matrix that matches.

Constraints

◆1 ≤ matrix.length, matrix[0].length ≤ 300
◆-10⁹ ≤ matrix[i][j], target ≤ 10⁹
◆Every row is sorted in ascending order, left to right
◆Every column is sorted in ascending order, top to bottom

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

🧪Try your own test case

matrix (rows separated by ;) — 1-4 rows, 1-5 cols, rows and columns sorted ascendingtarget

1	class Solution {
2	public boolean searchMatrixII(int[][] matrix, int target) {
3	int row = 0, col = matrix[0].length - 1;
4	while (row < matrix.length && col >= 0) {
5	int val = matrix[row][col];
6	if (val == target) {
7	return true;
8	} else if (val > target) {
9	col--;
10	} else {
11	row++;
12	}
13	}
14	return false;
15	}
16	}
17

↓cursor

Variables

row0

col2

INITIALIZE

Start at the top-right corner (0, 2) — the one cell where moving left strictly decreases value and moving down strictly increases it.

Step 1 / 4

Approach & Solutions

Brute Force — Scan Every Cell

Brute

Check every cell. Correct on any matrix, but this one doesn't have the row-major flattening trick from the simpler "Search a 2D Matrix" — rows and columns are each sorted independently, so a different idea is needed to beat O(m × n).

TimeO(m × n)

SpaceO(1)

Java

Try it out

class Solution {
    public boolean searchMatrixII(int[][] matrix, int target) {
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (matrix[i][j] == target) return true;
            }
        }
        return false;
    }
}

Optimal — Staircase Search from the Top-Right Corner

Optimal

Start at the top-right corner. From there, every move is informative: if the current value is too big, the entire column below it is also too big (columns increase downward) — so drop a row is wrong, move left instead. If it's too small, the entire row to its left is also too small — move down instead. Each step eliminates a whole row or column, giving O(m + n) instead of O(m × n).

TimeO(m + n)