CODEWITHSUNDEEP
data-structurestime-complexity
Abhishek Jaiswal
Abhishek Jaiswal

Reputation: 308

What would be the time complexity of the below-given code?

What would be the time complexity of findMaxArea function in the below-given code?

Question source: https://practice.geeksforgeeks.org/problems/length-of-largest-region-of-1s-1587115620/1#

class Solution:
    def dfs(self,i,j,grid,row,colm):
        if i<0 or j<0 or i>=row or j>=colm or grid[i][j]!=1:
            return 0
        res=0
        grid[i][j]=2
        res+=self.dfs(i+1,j,grid,row,colm)
        res+=self.dfs(i,j+1,grid,row,colm)
        res+=self.dfs(i+1,j+1,grid,row,colm)
        res+=self.dfs(i-1,j-1,grid,row,colm)
        res+=self.dfs(i-1,j,grid,row,colm)
        res+=self.dfs(i,j-1,grid,row,colm)
        res+=self.dfs(i+1,j-1,grid,row,colm)
        res+=self.dfs(i-1,j+1,grid,row,colm)
        return res+1
        

    #Function to find unit area of the largest region of 1s.
    def findMaxArea(self, grid):
        #Code here
        row=len(grid)
        colm=len(grid[0])
        maximum=-1
        for i in range(row):
            for j in range(colm):
                if grid[i][j]==1:
                    maximum=max(maximum,self.dfs(i,j,grid,row,colm))
        return maximum

#{ 
#  Driver Code Starts


if __name__ == '__main__':
    #T is number of test cases
    T=int(input())
    for i in range(T):
        #size of matrix n x m
        n, m = map(int, input().split())
        grid = []
        for _ in range(n):
            a = list(map(int, input().split()))
            grid.append(a)
        obj = Solution()
        ans = obj.findMaxArea(grid)
        print(ans)

# } Driver Code Ends

Upvotes: 0

Views: 43

Answers (1)

Harshini Komali
Harshini Komali

Reputation: 26

You are doing a dfs on a matrix to find the largest area of 1s.

Though you are making recursive calls, you visit each element only once in the worst-case scenario e.g. when the entire matrix is filled with 1's or the entire matrix is filled with 0's.

So the time complexity would be O(m*n) where m is the number of rows and n is the number of columns in the matrix.

Upvotes: 1

Related Questions