NeetCode 150: Search a 2D Matrix

Table of contents

The Problem

You are given an m x n integer matrix matrix with 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.

Given an integer target, return true if target is in matrix or false otherwise.

You must write a solution in O(log(m * n)) time complexity.

A Visual Example

Image taken from LeetCode.

The Approach

The goal is to carry out Binary Search for each dimension of the 2D Matrix. The first Binary Search attempt will search for the possible array that target could exist in. After we have located this array in matrix, this problem reduces to #704 Binary Search.

My Solution

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int minBound = 0;
        int maxBound = matrix.length - 1;

        // Binary Search to find the array target could be found in.
        while (maxBound >= minBound) {
            int midIndex = (maxBound + minBound) / 2;

            if (matrix[midIndex][0] == target) {
                return true;
                
            } else if (matrix[midIndex][0] > target) {
                maxBound = midIndex - 1;

            } else {
                minBound = midIndex + 1;
            }
        }

        // Takes the smaller index, minBound is assigned to 1 as
        // all the 0-index values were checked in the prev loop.
        int arrayIndex = getSmallerIndex(maxBound, minBound);
        minBound = 1;
        maxBound = matrix[arrayIndex].length - 1;

        // Binary Search to find the target in this array.
        while (maxBound >= minBound) {
            int midIndex = (maxBound + minBound) / 2;

            if (matrix[arrayIndex][midIndex] == target) {
                return true;

            } else if (matrix[arrayIndex][midIndex] > target) {
                maxBound = midIndex - 1;

            } else {
                minBound = midIndex + 1;
            }
        }
        return false;
    }

    // Returns the smaller index, correcting the value if it is < 0.
    private int getSmallerIndex(int a, int b) {
        if (a < b) {
            if (a < 0) {
                a++;
            }
            return a;
        } else {
            if (b < 0) {
                b++;
            }
            return b;
        }
    }
}

We first initialize the mininum and maxmimum boundaries, minBound & maxBound respectively, at the opposite ends of the array. The first while loop carries out Binary Search to locate the index of the array that target, using the 0 index values (return true if target exists in the 0-index) in the comparison for each array.

We retrieve the index of the array that target could exist in using getSmallerIndex() which returns the smaller index (& corrects it to be a valid index if required) between minBound & maxBound. Then, Binary Search is applied again on this array.

There are 3 scenarios when comparing the current element to target:

• If matrix[arrayIndex][midIndex] == target: target found, return true.
• If matrix[arrayIndex][midIndex] > target: The index of target only could exist “behind” midIndex. Set maxBound to midIndex - 1.
• If matrix[arrayIndex][midIndex] < target: The index of target only could exist “in front of” midIndex. Set minBound to midIndex + 1.

If the loop completes & no value is returned, means all values were considered and target does not exist in nums, returning false.