74. Search a 2D Matrix

In this tutorial we will solve 74. Search a 2D Matrix from leetcode.

Table of Content

• Reference
• Problem Statement
• Approach
• Code
• Complexity

Reference: 74. Search a 2D Matrix

Problem statement

In this problem statement we are given an input matrix of dimensions m * n where, m is the number of rows and n is the number of columns.

The matrix is 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.

We are asked to return true if the given integer value target is present in the matrix or false otherwise.

We are also instructed to find the result in O(log m*n) time complexity.

Example from leetcode.

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
-10^4 <= matrix[i][j], target <= 10^4

Approach

To solve this problem we will use Binary Search. By looking at the problem statement we can deduce that the target value, if present, will be in only one row of the given matrix. So, we can use Binary Search to first find the row in which the target value may exists. Next we will use the Binary Search to find the target value in the selected row.

Let us look at the first example matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3

target = 3

input

  | 0  1  2  3
--+-------------
0 | 1  3  5  7
1 | 10 11 16 20
2 | 23 30 34 60    


m = number of rows = matrix.length = 3
n = number of columns = matrix[0].length = 4

lastColIndex = n - 1 = 3


first we search the row

start = 0
end = m - 1 = 2

while start <= end ? yes
  mid = Math.floor((start+end) / 2)
      = Math.floor((0+2)/2)
      = 1

  so, we are inspecting row #1.

  is target >= first element of row #1 AND target <= last element of row #1 ?
  i.e., is 3 >= 10 AND 3 <= 20 ?
    => NO

  is target > last element of row #1 ?
  i.e., is 3 >= 20 ?
  	=> NO

  is target <= last element of row #1 ?
  i.e., is 3 <= 20 ?
    => YES
    => therefore, set end = mid - 1 = 0


start = 0
end = 0

while start <= end ? yes
  mid = Math.floor((start+end) / 2)
      = Math.floor((0+0)/2)
      = 0

  so, we are inspecting row #0.

  is target >= first element of row #0 AND target <= last element of row #0 ?
  i.e., is 3 >= 1 AND 3 <= 7 ?
    => YES
    => therefore, row #0 is or target row


now, we will perform binary search in row #0

start = 0
end = lastColIndex = 3

while start <= end ? YES
  mid = Math.floor((start+end) / 2)
      = Math.floor((0+3)/2)
      = 1

  is target == element #1 of row #0 ?
  i.e., 3 == 3 ?
    => YES
    => therefore, return true

Code

JavaScript

/**
 * @param {number[][]} matrix
 * @param {number} target
 * @return {boolean}
 */
var searchMatrix = function(matrix, target) {
    let targetRow = binarySearchRow(matrix, target);
    if (targetRow === -1) return false;
    return binarySearch(matrix[targetRow], target) !== -1;
};

const binarySearchRow = (matrix, target) => {
    let lastColIndex = matrix[0].length - 1;
    let start = 0
    let end = matrix.length - 1;
    while(start <= end) {
        let mid = Math.floor((start + end) / 2);
        if (target >= matrix[mid][0] && target <= matrix[mid][lastColIndex]) return mid;
        if (target > matrix[mid][lastColIndex]) start = mid + 1;
        else end = mid - 1;
    }
    return -1;
};

const binarySearch = (nums, target) => {
    let start = 0;
    let end = nums.length - 1;
    while(start <= end) {
        let mid = Math.floor((start + end) / 2);
        let midVal = nums[mid];
        if (midVal === target) return mid;
        if (midVal < target) start = mid + 1;
        else end = mid - 1;
    }
    return -1;
};

Complexity

Time complexity: O(log m*n)

The time complexity of this solution is O(log m*n)

Space complexity: O(1)

We are only using constant extra memory to solve the problem. Hence, space complexity is O(1).