Blogs Hub

by Sumit Chourasia | Oct 31, 2020 | Category :coding | Tags : algorithm array data-structure leetcode medium

Search a 2D Matrix - Array - Medium - LeetCode

Search a 2D Matrix - Array - Medium - LeetCode

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

Integers in each row are sorted from left to right.
The first integer of each row is greater than the last integer of the previous row.
 

Example 1:


Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,50]], target = 3
Output: true
Example 2:


Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,50]], target = 13
Output: false
Example 3:

Input: matrix = [], target = 0
Output: false
 

Constraints:

m == matrix.length
n == matrix[i].length
0 <= m, n <= 100
-104 <= matrix[i][j], target <= 104

public class Solution {
    public bool SearchMatrix(int[][] matrix, int target) {
        if(matrix.Length==0){
            return false;
        }
        
        int r = matrix.Length;
        int c = matrix[0].Length;
        int total = r*c;
        
        int lo = 0;
        int hi = total;
        while(lo<hi){
            int mid = lo + (hi-lo)/2;
            int row = mid/c;
            int col = mid%c;            
            if(matrix[row][col]> target){
                hi = mid;
            }
            else if(matrix[row][col]< target){
                lo = mid+1;
            }
            else if(matrix[row][col]==target){
                return true;
            }
            else{
                return false;
            }
        }
        
        return false;
    }
}

Time Complexity: O(logn)

Space Complexity: O(1)

Contributed By: Sumit Chourasia
Spiral Matrix - Array - Medium - LeetCode
Contributed By: Sumit Chourasia
Array Nesting - Array - Medium - LeetCode