DAY 82 - Search a 2D Matrix II

Hey Guys! Welcome to day 82 and we are going to solve today another leetcode problem.

Question: Search a 2D Matrix II

Write an efficient algorithm that searches for a value target in an m x n integer matrix matrix. This matrix has the following properties:

• Integers in each row are sorted in ascending from left to right.
• Integers in each column are sorted in ascending from top to bottom.

Example 1:

Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
Output: true

Intuition:

I don't think that the problem needs that much breakdown. It's a search question in matrix. It differs from the original question search in a matrix 1 such that it's elements are sorted row and column wise.

So now what can we do if the elements are sorted row wise and column wise.

Brute Force Approach:

• If we are to not think much and want to go through all the possible options, we do brute force.
• We simply traverse the matrix and return if we find our element.
• This is a high time complexity approach. In tight constraints it might fail so we need to find a better solution.

Better Approach:

• Let's take into the observation that we know the elements are sorted row wise.
• We know the start of a row and end of row are sorted.(Example start = i,0 && i,m-1).
• Let's try to apply binary search in that specific row and try to find our element.
• It would take us logM time to find the element in a row and n rows total, so it would be O(nlogM) approach.
• This is a good approach, let's try to code it out.

Code and Algo: Better Approach:

Algorithm and Code:

We will use a loop(say i) to select a particular row at a time.
Next, for every row, i, we will check if it contains the target using binary search.

After applying binary search on row, i, if we found any element equal to the target, we will return true. Otherwise, we will move on to the next row.

Finally, after completing all the row traversals, if we found no matching element, we will return false.

class Solution {
public:
    bool binarySearch(vector<int>& nums, int target){
        int n = nums.size(); 
        int low = 0, high = n - 1;


        while (low <= high) {
            int mid = (low + high) / 2;
            if (nums[mid] == target) return true;
            else if (target > nums[mid]) low = mid + 1;
            else high = mid - 1;
        }
        return false;
    }

    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int n = matrix.size();

        for (int i = 0; i < n; i++) {
            bool flag =  binarySearch(matrix[i], target);
            if (flag) return true;
        }
        return false;

    }
};

Optimal Approach:

• Let's observe the matrix and we know in binary search we know we have a start and end.
• If we were to apply binary search here we need a start. Let's consider the 4 corners as our starting points. Assume the given target to be 14.
• If we were to start from position(0,0). We check as usual if our element is greater or bigger. Since it's bigger we need to go towards the end but since both the column and row is increasing as we go, we can't decide where should we move tactfully. So let's put this starting point on hold.
• Similarly if we were to start from position(n-1,m-1) we will find our element to be smaller than or equal to as it's the last element. Normally it would be smaller, so we need to go towards the start but again we are in a clutch as both row and column are decreasing.

• Let's take the stating point to be (0,m-1).Now, in this case, the row is in decreasing order and the column is in increasing order. Therefore, if we start traversal from (0, m-1), in the following way, we can easily determine how we should move.

• If matrix[0][m-1] > target: We should move row-wise.

• If matrix[0][m-1] < target: We need bigger elements and so we should move column

Using this intuition we will write the code and algorithm for this.

Algorithm and Code:

• Initialize rowIndex to 0 and colIndex to the last column index (col - 1).
• Enter a loop that continues as long as both rowIndex is within the valid row range (< row) and colIndex is within the valid column range (>= 0).
• Get the element at the current position (matrix[rowIndex][colIndex]).
• Compare the element with the target value:
• If the element is equal to the target, return true as the target value is found in the matrix.
• If the element is less than the target, move the search down by incrementing rowIndex.
• If the element is greater than the target, move the search left by decrementing colIndex.
• Repeat steps 3-4 until the search area is exhausted (i.e., rowIndex is out of range or colIndex is out of range).
• If the loop completes without finding the target value, return false.

bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int row = matrix.size();
        int col = matrix[0].size();

        int rowIndex = 0;
        int colIndex = col-1;

        while(rowIndex < row && colIndex >=0)
        {
            int element = matrix[rowIndex][colIndex];
            if(element == target)
            return true;
            else if (element < target)
            {
                rowIndex++;
            }
            else{
                colIndex--;

            }
        }
        return false;
    }

Complexity Analysis:

Thanks for reading!. Feedback is highly appreciated!