Search a 2D Matrix · Interview Problem

Back to problems

Leetcode

Medium

Arrays

Binary Search

Matrices

Google

Search a 2D Matrix

Search for a target value in a matrix with sorted rows and row-to-row ordering.

Acceptance 0%

Start Practice

Problem Statement

Problem

You are given a 2D matrix of integers with m rows and n columns.

The matrix has the following 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 a target value, determine whether it exists in the matrix.

Return true if the target is present, otherwise return false.

Intuition

Because the rows are ordered globally, the entire matrix can be treated like a single sorted array for searching.

Input Format

The first line contains two integers m and n.
The next m lines each contain n integers describing the matrix.
The final line contains the integer target.

Output Format

Print true if target exists in the matrix.
Otherwise print false.

Constraints

1 <= m, n
The matrix is row-wise sorted in non-decreasing order.
The first element of each row is strictly greater than the last element of the previous row.
Integers may be negative or positive.

Examples

Sample cases returned by the problem API.

Example 1

Input

3 4
1 3 5 7
10 11 16 20
23 30 34 60
3

Output

true

Explanation

The target 3 appears in the first row.

Example 2

Input

3 4
1 3 5 7
10 11 16 20
23 30 34 60
13

Output

false

Explanation

The target 13 does not appear anywhere in the matrix.

Premium problem context

Unlock deeper context for this problem

Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.

Guided hints

Editorial and discussion links

Concept map and variants

Track your progress