Today’s problem

https://leetcode.com/problems/maximum-number-of-fish-in-a-grid/description/

Intuition

Find the size of the connected blocks.

Approach

Iterate through the grid to add the size to a connected block, then find the maximum size of the connected block.

Complexity

  • Time complexity: $O(N\times M)$, we will visit every point exactly once.

  • Space complexity: $O(1)$, if you do not count the original grid.

Code

class Solution:
    def findMaxFish(self, grid: List[List[int]]) -> int:
        ans = 0
        dx = [0,0,1,-1]
        dy = [1,-1,0,0]
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == 0:
                    continue
                tmp = grid[i][j]
                grid[i][j] = 0
                q = deque([(i,j)])
                while len(q) > 0:
                    x,y = q.popleft()
                    for k in range(4):
                        nx = x + dx[k]
                        ny = y + dy[k]
                        if nx < 0 or ny < 0 or nx >= len(grid) or ny >= len(grid[0]) or grid[nx][ny] == 0:
                            continue
                        
                        tmp += grid[nx][ny]
                        grid[nx][ny] = 0
                        # print(i,j,nx, ny, tmp)
                        q.append((nx, ny))
                
                ans = max(ans, tmp)
    
        print(grid)

        return ans