Start learning free

LESSON 326 OF 536 · BINARY SEARCH

Search a 2D Matrix in JavaScript: O(log(m·n)) Binary Search

Practice O(log(m · n)) Read the full explanation

You are given a matrix of integers matrix with m rows and n columns, and an integer target. The matrix has two properties:

Each row is sorted in non-decreasing order.
The first value of each row is greater than the last value of the row before it.

Return true if target is in matrix, or false otherwise.

The matrix is an array of rows, and each row is an array of integers. Rows are numbered from 0, top to bottom, and columns from 0, left to right.

Example 1:

Input: matrix = [
  [1, 3, 5, 7],
  [10, 11, 16, 20],
  [23, 30, 34, 60]
], target = 3
Output: true
Explanation: 3 is in row 0, column 1.

Example 2:

Input: matrix = [
  [1, 3, 5, 7],
  [10, 11, 16, 20],
  [23, 30, 34, 60]
], target = 13
Output: false
Explanation: 13 would sit between 11 and 16 in row 1, but it isn't there.

Example 3:

Input: matrix = [
  [1, 3, 5, 7],
  [10, 11, 16, 20],
  [23, 30, 34, 60]
], target = 30
Output: true
Explanation: Read row by row, the 12 values form one sorted list:
1, 3, 5, 7, 10, 11, 16, 20, 23, 30, 34, 60.
30 is at position 9 of that list (counting from 0), which is row 2, column 1.

Constraints:

1 <= m, n <= 1000
-10⁹ <= matrix[i][j], target <= 10⁹
Every row has n values, sorted in non-decreasing order, and each row starts with a value greater than the last value of the row before it.

Note:

Your algorithm should run in O(log(m · n)) time and use O(1) extra space. Checking every cell would take O(m · n).

STEP 1 OF 9

Guided

Ctrl + Enter to check

JAVASCRIPT · BINARY SEARCH

Search A 2d Matrix in JavaScript, explained

Problem overview

The method searchMatrix receives matrix, an array of rows where each row is an array of numbers, and a number target. It returns true if target appears anywhere in the matrix and false otherwise.

The matrix has two properties. Every row is sorted in non-decreasing order, and the first value of each row is greater than the last value of the row before it. Take this matrix:

[
  [1, 3, 5, 7],
  [10, 11, 16, 20],
  [23, 30, 34, 60]
]

With target = 3 the answer is true (row 0, column 1). With target = 13 it is false: 13 would sit between 11 and 16, but it isn't there. With target = 30 it is true (row 2, column 1).

The statement asks for O(log(m · n)) time and O(1) extra space, where m is the number of rows and n the number of columns.

Approach: one sorted list in disguise

Checking every cell works, but it takes O(m · n) time. The two properties allow much more. Read the rows one after another and the values never go down: the last value of a row is smaller than the first value of the next row. So the whole matrix behaves like a single sorted list of m * n values. For the matrix above that list is 1, 3, 5, 7, 10, 11, 16, 20, 23, 30, 34, 60.

A sorted list can be searched with binary search: look at the middle, discard the half that cannot contain the target, repeat. The only obstacle is that the list doesn't exist as an array. We don't need to build it, since building it would cost O(m · n) time and space. Instead, we binary search over the positions 0 to m * n - 1 and convert a position into a row and a column whenever we need its value.

The conversion uses the row length. Every row holds n values, so the positions before position p fill Math.floor(p / n) complete rows, and p % n more cells of the next one. That makes the row Math.floor(p / n) and the column p % n. With 4 columns, position 9 is row 2, column 1.

Step by step

Read the dimensions. The number of rows is matrix.length. Every row has the same length, so the number of columns is the length of the first row.
Set the search range to the positions of the imagined list: left is 0 and right is m * n - 1. Both ends are inclusive, so right is the last position itself.
Loop while left <= right. With <=, a range holding a single position still gets checked. A strict < would skip it.
Find the middle position. Take left plus half the distance to right, rounded down with Math.floor. In JavaScript, / never truncates, so 7 / 2 is 3.5 and a position needs the explicit rounding.
Turn the position into a cell. The row is Math.floor(middle / n) and the column is middle % n. Store the value found there.
If the value equals target, return true.
If the value is smaller, the target can only be later, so move left to middle + 1. Using middle + 1 rather than middle matters: the value at middle is already ruled out, and keeping it in the range could make the loop run forever.
Otherwise the value is bigger, so move right to middle - 1.
After the loop, no position is left to check, so return false.

The solution in JavaScript

class Solution {
    searchMatrix(matrix, target) {
        let m = matrix.length, n = matrix[0].length;
        let left = 0, right = m * n - 1;
        while (left <= right) {
            let middle = Math.floor(left + (right - left) / 2);
            let value = matrix[Math.floor(middle / n)][middle % n];
            if (value == target) {
                return true;
            } else if (value < target) {
                left = middle + 1;
            } else {
                right = middle - 1;
            }
        }
        return false;
    }
}

Some JavaScript details worth a closer look:

Division gives a fraction. 9 / 4 is 2.25, and an array can't be indexed with 2.25: matrix[2.25] is undefined, and reading [1] from it throws a TypeError. That's why the row is Math.floor(middle / n). The column middle % n is already a whole number when middle is.
== and ===. The solution compares with ==, which converts types when they differ. Both sides are numbers here, so it behaves like ===, and === is the safer habit in general.
Two comma-separated declarations. let m = ..., n = ...; declares both variables in one statement. It is the same as two separate let lines.
Numbers are doubles. The positions here stay far below 2^53 (at most a million for a 1000 by 1000 matrix), so every position is exact.

Tracing target = 30

The matrix above has m = 3 and n = 4, so the positions run from 0 to 11. Searching for 30 gives this trace:

left	right	middle	row	column	value	decision
0	11	5	1	1	11	too small, left = 6
6	11	8	2	0	23	too small, left = 9
9	11	10	2	2	34	too big, right = 9
9	9	9	2	1	30	found, return true

Complexity

Time: O(log(m · n)). Each pass of the loop halves the number of positions still in play, so the loop runs about log2(m · n) times: around 20 passes for a million cells. Each pass does a fixed amount of work.

Space: O(1). The code keeps a handful of numbers. It finds a cell by arithmetic and never copies the matrix into a flat array.

Edge cases and common mistakes

A single cell. [[5]] with target 5 returns true, and with target 4 it returns false. The range holds one position, which only the <= loop condition checks.
A single column or a single row. [[1], [3], [5]] with target 3 returns true, and [[1, 3, 5]] with target 4 returns false. The arithmetic works for any shape.
Targets outside the range. A target below the first value (such as 0) or above the last (such as 61) returns false after the range shrinks to nothing.
Using the number of rows where the number of columns belongs. The row is middle / n and the column is middle % n, with n the row length. Swapping the roles points at the wrong cells.
Forgetting Math.floor. The row index becomes a fraction and the lookup fails.
Moving to middle instead of middle + 1 or middle - 1. The range can stop shrinking, and the loop never ends.
Searching row by row with a full scan inside. That is correct but costs O(m · n), which the statement rules out.

Testing

With the 3 by 4 matrix from the problem overview:

target 3 gives true.
target 13 gives false.
target 30 gives true.
target 1 (the first value) gives true.
target 60 (the last value) gives true.
target 0 gives false.
target 61 gives false.

Keep going with JavaScript500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free