74. Search a 2D Matrix

Search a 2D Matrix (LeetCode 74) is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Binary Search Patterns pattern, in the On Sorted Array/List subpattern.

• NeetCode 150 · #29 of 150 · Binary Search
• NeetCode 250 · #64 of 250 · Binary Search

How to solve Search a 2D Matrix

Search a 2D Matrix is a Binary Search on Sorted Array problem, part of Binary Search Patterns. Master standard binary search on sorted arrays. Learn search insert position, sqrt calculation, and 2D matrix search.

Work towards the solution in these steps:

1. Consider how you might leverage the sorted nature of the matrix to efficiently search for the target.
2. Think about flattening the 2D matrix conceptually into a 1D sorted array without actually modifying the original matrix.
3. How can you map a single index in this conceptual 1D array back to the corresponding row and column in the 2D matrix?

The reference solution runs in O(logm + logn) time and O(1) space.

The Search a 2D Matrix solution and editorial walks through the full approach with reference code.

Problem statement

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

- -104 <= matrix[i][j], target <= 104

Topics and companies

Topics: Array, Binary Search, Matrix.

Reported in interviews at Amazon, Facebook, Apple, Microsoft, Nvidia.

How to practise Search a 2D Matrix on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(logm + logn) time and O(1) space.

Open Search a 2D Matrix in the code editor, or read the Search a 2D Matrix editorial for a worked solution with its approach and complexity analysis.

Where Search a 2D Matrix sits in the DSA pattern sheet

• Binary Search Patterns pattern guide
• On Sorted Array/List subpattern
• The full DSA patterns sheet

Problems related to Search a 2D Matrix

Other problems that use the same On Sorted Array/List and Binary Search Patterns techniques:

• Binary Search — Easy, same subpattern
• First Bad Version — Easy, same subpattern
• Guess Number Higher or Lower — Easy, same subpattern
• Kth Missing Positive Number — Easy, same subpattern
• Search Insert Position — Easy, same subpattern
• Single Element in a Sorted Array — Medium, same subpattern

Search a 2D Matrix FAQ