Start learning free

LESSON 330 OF 540 · BINARY SEARCH

Search a 2D Matrix in Scala: 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
  • -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

    SCALA · BINARY SEARCH

    Search A 2d Matrix in Scala, explained

    Problem overview

    The method searchMatrix receives a matrix as an Array[Array[Int]], an array of rows, and an integer target. It returns true when the target appears somewhere in the matrix and false otherwise. Two properties hold: 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.

    Take the matrix with rows [1, 3, 5, 7], [10, 11, 16, 20] and [23, 30, 34, 60]. The target 3 is in row 0, column 1, so the answer is true. The target 13 would sit between 11 and 16 in row 1, but it isn't there, so the answer is false.

    Approach: treat the matrix as one sorted list

    Checking every cell costs O(m · n). The statement asks for O(log(m · n)) time and O(1) extra space, which points to binary search.

    The two properties together mean that reading the rows one after another gives a single sorted list of m * n values. For the example it is 1, 3, 5, 7, 10, 11, 16, 20, 23, 30, 34, 60. We don't build that list, because copying it would cost O(m · n) space. We only imagine it, and binary search the positions 0 to m * n - 1. The one thing we need is a way to turn a position into a cell.

    Every row holds n values, so the positions before middle fill middle / n whole rows and middle % n cells of the next one. Row is middle / n, column is middle % n. With 4 columns, position 9 is row 2, column 1, which holds 30.

    Each pass compares the value at the middle position with the target and throws away half of the positions, so the loop runs about log2(m · n) times: around 20 passes for a million cells.

    Step by step

    1. Store the dimensions. m is matrix.length, the number of rows, and n is matrix(0).length. Every row has the same length, so the first row tells the number of columns.
    2. Set the search bounds. left is 0 and right is m * n - 1, the last position. Both are vars because the search moves them, and both are inclusive.
    3. Loop while left <= right. When the two are equal, one position is still unchecked, so a strict < would skip it.
    4. Find the middle as left + (right - left) / 2. Integer division rounds down, and adding half the distance to left can't overflow the way left + right can.
    5. Convert the position to a cell and read its value: row middle / n, column middle % n. Scala indexes with parentheses, row first.
    6. Return true if the value equals the target.
    7. If the value is smaller, the target can only be later, so left becomes middle + 1.
    8. Otherwise the value is bigger, so right becomes middle - 1.
    9. Return false after the loop: every position that could hold the target has been ruled out.

    The solution in Scala

    class Solution {
    def searchMatrix(matrix: Array[Array[Int]], target: Int): Boolean = {
        val m = matrix.length
        val n = matrix(0).length
        var left = 0
        var right = m * n - 1
        while (left <= right) {
            val middle = left + (right - left) / 2
            val value = matrix(middle / n)(middle % n)
            if (value == target) {
                return true
            } else if (value < target) {
                left = middle + 1
            } else {
                right = middle - 1
            }
        }
        return false
    }
}

    The Scala details worth a closer look:

    • Two sets of parentheses. matrix(middle / n) is the row, an Array[Int], and the second pair of parentheses indexes into that row. There is no matrix[i][j] syntax: in Scala, matrix(i)(j) is a call to apply on the array, twice.
    • return inside a loop. The last expression of a block is its value, so most Scala code leaves return out. Here the early return true leaves the while loop at once, which is the clearest way to stop the search. A while loop itself has no value, so the method still needs its final line.
    • val and var. m, n, middle and value never change after they are set, so they are vals. Only left and right move.
    • Int division and remainder. 9 / 4 is 2 and 9 % 4 is 1, which is how position 9 becomes row 2, column 1.

    Complexity

    Time: O(log(m · n)). The range of positions halves on every pass, and each pass does constant work: one division, one remainder and one comparison. This equals O(log m + log n).

    Space: O(1). The method keeps a handful of integers. The cell is found by arithmetic, and no flattened copy of the matrix is made.

    Edge cases and common mistakes

    • A single cell. For [[5]], left and right both start at 0. Target 5 returns true and target 4 returns false. This is where <= matters.
    • One column or one row. For rows [1], [3], [5] and target 3, n is 1, so every position is its own row and the column is always 0. For the single row [1, 3, 5], middle / n is always 0. Both work with no special case.
    • Targets outside the range. 0 is smaller than everything and 61 is bigger than everything in the example. Both end with false after the search runs out of positions.
    • Swapping the divisor. Dividing by m instead of n gives wrong cells whenever the matrix isn't square, and may index out of bounds. Rows are found with the number of columns.
    • Keeping middle in the range. Writing left = middle or right = middle can loop forever, because the position just checked stays in range. Use middle + 1 and middle - 1.
    • Overflow in the midpoint. Int is 32 bits and overflow wraps silently in Scala. With left = 2000000000 and right = 2100000000, (left + right) / 2 gives -97483648, while left + (right - left) / 2 gives 2050000000. The matrix here has at most a million cells, so either form works, but the second form is the safe habit.

    Testing

    For the example matrix with rows [1, 3, 5, 7], [10, 11, 16, 20] and [23, 30, 34, 60]:

    • target 3 gives true;
    • target 13 gives false;
    • target 30 gives true: the search checks positions 5, 8, 10 and 9, which hold 11, 23, 34 and 30;
    • target 1 and target 60, the first and last cells, both give true;
    • target 0 and target 61 both give false.

    The matrix [[5]] with target 5 gives true, and with target 4 gives false.

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