Start learning free

LESSON 330 OF 540 · BINARY SEARCH

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

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
  • -109 <= matrix[i][j], target <= 109
  • 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
    Ctrl + Enter to check

    TYPESCRIPT · BINARY SEARCH

    Search A 2d Matrix in TypeScript, explained

    Problem overview

    The method searchMatrix(matrix, target) receives a matrix of integers, an array of rows where each row is a number[], 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 above it. For [[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]], the target 3 gives true (row 0, column 1), the target 13 gives false (it would sit between 11 and 16, but it isn't there), and the target 30 gives true (row 2, column 1).

    The budget is O(log(m · n)) time and O(1) extra space, where m is the number of rows and n the number of columns. Checking every cell takes O(m · n), which is too slow.

    Approach: treat the matrix as one sorted list

    Read the rows one after another and the values never go down: each row is sorted, and each row starts above where the previous one ended. So the 12 values of the example form one sorted list: 1, 3, 5, 7, 10, 11, 16, 20, 23, 30, 34, 60. Sorted data is what binary search needs.

    The catch is that the data is not stored as one list, and building one would cost O(m · n) time and space. The way out is to search over positions from 0 to m * n - 1 and convert a position into a cell only when we need its value. With n values per row, position p lies in row Math.floor(p / n) and column p % n. In the example n is 4, so position 9 is row 2, column 1, and that cell holds 30.

    Each pass of the loop throws away half of the remaining positions, so a matrix with a million cells needs about 20 passes. Nothing is allocated beyond a handful of numbers, so the extra space is constant.

    Step by step

    1. Measure the matrix. m is the number of rows, matrix.length, and n is the length of the first row. Every row has the same length, so the first one is enough.
    2. Set the search range to the positions left = 0 to right = m * n - 1. Both ends are inclusive: right is the last position itself.
    3. Loop while left <= right. When the two are equal, one position is still unchecked, which is why the condition is <= and not <.
    4. Take the middle position as left + (right - left) / 2, rounded down with Math.floor. In TypeScript / always gives a floating-point result, so without Math.floor an odd distance would leave x.5, which is not a position.
    5. Turn the position into a cell with Math.floor(middle / n) for the row and middle % n for the column, and read value from there.
    6. If value equals target, return true at once.
    7. If value is smaller than target, the target can only be at a later position, so move left to middle + 1. The position middle itself has just been checked, so keeping it in the range could make the loop run forever.
    8. Otherwise value is too big: move right to middle - 1.
    9. After the loop, no position is left to check, so return false.

    The solution in TypeScript

    class Solution {
    searchMatrix(matrix: number[][], target: number): boolean {
        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;
    }
}

    TypeScript details worth knowing

    number is a double-precision float, so 7 / 2 is 3.5, not 3. That is why both the middle position and the row index use Math.floor. The column needs no rounding: % on whole numbers always gives a whole number.

    The type annotations (number[][], boolean) are checked by the compiler and erased from the JavaScript it produces. They do nothing at run time.

    The formula left + (right - left) / 2 gives the same result as (left + right) / 2. The first form is the classic way to avoid integer overflow in languages with fixed-size integers. A TypeScript number doesn't overflow here (the largest position is about a million), so both forms work, but the habit is worth keeping.

    The lesson's code compares with ==. For two numbers it behaves like ===; in your own code === is the safer default, because == converts values of different types before comparing them.

    Tracing the search

    For the target 30 in the example matrix, n is 4 and the positions run from 0 to 11:

    leftrightmiddlecellvalueaction
    0115row 1, column 11111 < 30, so left = 6
    6118row 2, column 02323 < 30, so left = 9
    91110row 2, column 23434 > 30, so right = 9
    999row 2, column 130found, return true

    Four reads instead of up to twelve. When the target is missing, the range shrinks until left passes right and the loop ends.

    Complexity

    Time: O(log(m · n)). The range starts with m * n positions and loses about half of them on every pass, so there are at most about log2(m · n) passes. Each pass does a constant amount of work: one division, one remainder and one array read.

    Space: O(1). The code keeps a few numbers and never copies the matrix or builds a flat list.

    Edge cases and common mistakes

    • A single cell. With [[5]], m * n - 1 is 0, the loop runs once, and the target 5 gives true while 4 gives false.
    • A single row or a single column. [[1, 2, 3]] has n = 3, and [[1], [3], [5]] has n = 1, so every position is its own row and the column is always 0. The same code handles both.
    • Dividing by the wrong size. The row index divides by n, the number of columns, not by m. Mixing them up works for square matrices and fails for others.
    • Forgetting Math.floor on the row. middle / n is usually a fraction, and indexing an array with a fraction gives undefined, so the next read throws.
    • Using left < right. The loop would stop one position early and miss a target that sits in the last remaining position.
    • Setting left = middle or right = middle. The range may stop shrinking and the loop never ends. Always move past the position you just checked.

    Testing

    With the example matrix, the lesson's code gives these results:

    target 3   -> true
target 13  -> false
target 30  -> true
target 1   -> true   (the first cell)
target 60  -> true   (the last cell)
target 0   -> false  (smaller than everything)
target 61  -> false  (bigger than everything)

    Try the same targets in the editor above, then a one-cell matrix and a one-column matrix.

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