Syed Jafer K

Its all about Trade-Offs

POTD #2 Search in a Row-Column sorted matrix | Geeks For Geeks

Second day of POTD Geeks For Geeks. https://www.geeksforgeeks.org/problems/search-in-a-matrix17201720/1.

Given a 2D integer matrix mat[][] of size n x m, where every row and column is sorted in increasing order and a number x,the task is to find whether element x is present in the matrix.

Examples:


Input: mat[][] = [[3, 30, 38],[20, 52, 54],[35, 60, 69]], x = 62
Output: false
Explanation: 62 is not present in the matrix, so output is false.


Input: mat[][] = [[18, 21, 27],[38, 55, 67]], x = 55
Output: true
Explanation: 55 is present in the matrix.

My Approach

The question states that every row in the matrix is sorted in ascending order. So we can use the binary search to find the element inside each array.

So ,

  1. Iterate each array of the matrix.
  2. Find the element in array using binary search.

#User function Template for python3
class Solution:
    
    def binary_search(self, arr, x, start, stop):
        if start > stop:
            return False
        mid = (start + stop) // 2
        if start == stop and arr[start] != x:
            return False
        if arr[mid] == x:
            return True
        elif arr[mid] > x:
            return self.binary_search(arr, x, start, mid)
        else:
            return self.binary_search(arr, x, mid+1, stop)
        
        
    
    def matSearch(self, mat, x):
        # Complete this function
        for arr in mat:
            result = self.binary_search(arr, x, 0, len(arr)-1)
            if result:
                return True
        return False