LeetCode Problems

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

Reference: 74. Search a 2D Matrix

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.

Watch this video for Binary Search.

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
```

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
```

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;
};
```

**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).

ADVERTISEMENT