Question

You are given an m x n 2-D integer array matrix and an integer target.

• Each row in matrix is sorted in non-decreasing order.

• The first integer of every row is greater than the last integer of the previous row.

Return true if target exists within matrix or false otherwise.

Example 1

Input: matrix = [[1,2,4,8],[10,11,12,13],[14,20,30,40]], target = 10

Output: true

Example 2

Input: matrix = [[1,2,4,8],[10,11,12,13],[14,20,30,40]], target = 15

Output: false

Approach

To solve this problem, we have two approach. Brute Force and Binary Search.

Brute Force

We will use a for loop to iterate through the matrix, applying binary search to each array to determine if the target exists. The time complexity is O(n log m), where n is the number of arrays in the matrix and m is the length of each individual array.

Algorithm

1. For index i from 0 to length of matrix

   1. Create two variables left and right to store start of array and end of array.

   2. While left <= right:

      1. Compute the mid of array

      2. Check if element at mid is equal to target, then return true

      3. Else if element at mid is greater than target, then decrement right

      4. Else increment left

2. After the loop, return false.

Solution (JS code)

class Solution {
    /**
     * @param {number[][]} matrix
     * @param {number} target
     * @return {boolean}
     */

    searchMatrix(matrix, target) {        
        for (let m of matrix) {
            let l = 0;
            let r = m.length-1;

            while (l <= r) {
                let mid = Math.trunc((l+r)/2);

                if (m[mid] === target) {
                    console.log("mid : ", m[mid])
                    return true
                }
                else if (m[mid] > target) {
                    r = mid - 1;
                }
                else {
                    l = mid + 1;
                }
            }
        }

        return false;
    }
}

Time Complexity

O(n log m)

Space Complexity

O(1)

Binary Search

Instead of apply binary search inside the for loop, we can convert the 2d matrix in 1d array and then we can apply binary search. This way the time complexity will be O(log (m * n)) and space complexity will be O(1).

Algorithm

1. Store number of rows and cols in variables.

2. Create variables left = 0 and right = rows * cols - 1

3. While left <= right:

   1. Compute mid = left + right / 2

   2. Compute row = Math.floor(mid / cols) and col = mid % cols

   3. Check if element at row and col is greater than target then update right = mid - 1

   4. Else if element at row and col is less than target then update left = mid + 1

   5. Else return true

4. After the loop, return false

Solution (JS code)

class Solution {
    /**
     * @param {number[][]} matrix
     * @param {number} target
     * @return {boolean}
     */
    searchMatrix(matrix, target) {
        let ROWS = matrix.length,
            COLS = matrix[0].length;

        let l = 0,
            r = ROWS * COLS - 1;
        while (l <= r) {
            let m = l + Math.floor((r - l) / 2);
            let row = Math.floor(m / COLS),
                col = m % COLS;
            if (target > matrix[row][col]) {
                l = m + 1;
            } else if (target < matrix[row][col]) {
                r = m - 1;
            } else {
                return true;
            }
        }
        return false;
    }
}

Time Complexity

O(log (ROWS * COLS))

Space Complexity

O(1)