Search a 2D Matrix II Leetcode Solution

Difficulty Level Medium
Frequently asked in Amazon Apple Bloomberg Facebook Microsoft Oracle
Array Binary Search Divide and Conquer MatrixViews 3525

Problem Statement

The Search a 2D Matrix II LeetCode Solution – “Search a 2D Matrix II”asks you to find an efficient algorithm that searches for a value target in an m x n integer matrix matrix. Integers in each row, as well as column, are sorted in ascending order.

Example:

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

Explanation:

  • We can easily observe that the matrix contains the target value, hence true is our answer.
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 = 20
Output: false

Explanation:

  • Matrix doesn’t contain the target value, hence false is returned.

Approach

Idea:

  1. The main idea to solve this problem is to take advantage of sorted rows and sorted columns.
  2. Start from the cell (0,n-1).
  3. Compare the cell value with the target:
    1. If they are equal, return true.
    2. If the cell value is strictly more than the target, it means that the target will never lie in the current column since all the values in the current column that are at a higher index row than the current row index, will have strictly more value than the current cell. Hence, we decrement the current column index to search for the target.
    3. If the cell value is strictly less than the target, it means that the target will never lie in the current row since all the values in the current row that are at a lower index than the current column index, will have strictly less value than the current cell. Hence, we increment the current row index to search for the target.

Search a 2D Matrix II Leetcode Solution

The fact that the matrix is sorted suggests that there must be some way to use binary search to speed up our algorithm. You can also apply Binary Search.

Code for Search a 2D Matrix II Leetcode Solution:

C++ Solution:

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size(),n = matrix[0].size(),i = 0,j = n - 1;
        while(i<m && j>=0){
            if(matrix[i][j]==target){
                return true;
            }
            else if(matrix[i][j]>target){
                j--;
            }
            else{
                i++;
            }
        }
        return false;
    }
};

Java Solution:

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length,n = matrix[0].length,i = 0,j = n - 1;
        while(i<m && j>=0){
            if(matrix[i][j]==target){
                return true;
            }
            else if(matrix[i][j]>target){
                j--;
            }
            else{
                i++;
            }
        }
        return false;
    }
}

Complexity Analysis for Search a 2D Matrix II Leetcode Solution

Time Complexity

The time complexity of the above code is O(M+N) since the overall maximum number of iterations goes to m + n.

Space Complexity

The space complexity of the above code is O(1) since we’re using the constant space.

Reference: https://en.wikipedia.org/wiki/Binary_search_algorithm

Translate »