❌

Normal view

There are new articles available, click to refresh the page.
Before yesterdayMain stream

POTD #4 – Search in a sorted Matrix | Geeks For Geeks

✇Parotta Salna
By: Mr.ParottaSalna
24 December 2024 at 06:29

Problem Statement

Geeks For Geeks – https://www.geeksforgeeks.org/problems/search-in-a-matrix-1587115621/1

Given a strictly sorted 2D matrix mat[][] of size n x m anda number x. Find whether the number x is present in the matrix or not.


Note: In a strictly sorted matrix, each row is sorted in strictly increasing order, and the first element of the ith row (i!=0) is greater than the last element of the (i-1)th row.


Input: mat[][] = [[1, 5, 9], [14, 20, 21], [30, 34, 43]], x = 14
Output: true
Explanation: 14 is present in the matrix, so output is true.

My Approach

Today’s problem is same as yesterday’s problem. 


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)
    
    #Function to search a given number in row-column sorted matrix.
    def searchMatrix(self, mat, x): 
    	# code here 
    	length = len(mat[0]) - 1
        for arr in mat:
            result = self.binary_search(arr, x, 0, length)
            if result:
                return True
        return False

POTD #3 Search in a row-wise sorted matrix | Geeks For Geeks

✇Parotta Salna
By: Mr.ParottaSalna
23 December 2024 at 10:25

Problem Statement

GFG Link – https://www.geeksforgeeks.org/problems/search-in-a-row-wise-sorted-matrix/1

Given a row-wise sorted 2D matrix mat[][] of size n x m andan integer x, find whether element x is present in the matrix.
Note: In a row-wise sorted matrix, each row is sorted in itself, i.e. for any i, j within bounds, mat[i][j] <= mat[i][j+1].

Input: mat[][] = [[3, 4, 9],[2, 5, 6],[9, 25, 27]], x = 9
Output: true
Explanation: 9 is present in the matrix, so the output is true.


Input: mat[][] = [[19, 22, 27, 38, 55, 67]], x = 56
Output: false
Explanation: 56 is not present in the matrix, so the output is false.

My Approach:

Today’s problem is same as yesterday’s problem. But i got timed out. So instead of calculating the len(arr) each time (which is same always ) i just stored it in a variable and passed. 

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:
            result = self.binary_search(arr, x, 0, length)
        elif arr[mid] > x:
            return self.binary_search(arr, x, start, mid)
        else:
            return self.binary_search(arr, x, mid+1, stop)
    
    #Function to search a given number in row-column sorted matrix.
    def searchRowMatrix(self, mat, x): 
    	# code here 
    	length = len(mat[0]) - 1
    	for arr in mat:
            result = self.binary_search(arr, x, 0, length)
            if result:
                return True
        return False

❌
❌