You are given a 0-indexed 2D matrix grid of size m x n, where (r, c) represents:
grid[r][c] = 0, orgrid[r][c] fish, if grid[r][c] > 0.A fisher can start at any water cell (r, c) and can do the following operations any number of times:
(r, c), orReturn the maximum number of fish the fisher can catch if he chooses his starting cell optimally, or 0 if no water cell exists.
An adjacent cell of the cell (r, c), is one of the cells (r, c + 1), (r, c - 1), (r + 1, c) or (r - 1, c) if it exists.
Example 1:
Input: grid = [[0,2,1,0],[4,0,0,3],[1,0,0,4],[0,3,2,0]] Output: 7 Explanation: The fisher can start at cell(1,3)and collect 3 fish, then move to cell(2,3)and collect 4 fish.
Example 2:
Input: grid = [[1,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,1]] Output: 1 Explanation: The fisher can start at cells (0,0) or (3,3) and collect a single fish.
Constraints:
m == grid.lengthn == grid[i].length1 <= m, n <= 100 <= grid[i][j] <= 10This approach involves treating the grid as a graph and using depth-first search to explore each connected component of water cells. The goal is to aggregate the number of fish in each connected component and return the maximum number encountered. We start from each unvisited water cell and attempt to explore the maximum number of fish that can be collected from that starting point using DFS.
The function dfs is a recursive implementation of depth-first search, used to explore all reachable water cells starting from a given cell. It aggregates the fish count for a connected component. The main function maxFish iterates through all cells, starting a DFS search whenever an unvisited water cell is encountered. The maximum fish count from all searches is tracked and returned as the result.
C++
Java
Python
C#
JavaScript
Time Complexity: O(m*n), where m and n are the dimensions of the grid. Each cell is visited once.
Space Complexity: O(m*n), to store the visited state of each cell.
This alternative approach uses breadth-first search to traverse each component of water cells in the grid. Instead of exploring depth-first, it explores all neighbor cells at the present "depth" before moving deeper. The total number of fish for each component is counted, with the goal of finding the maximum possible collection.
This C code uses BFS via a queue to explore each connected group of water cells starting from an unvisited starting cell. It maintains a queue to store cells to be visited, and each cell is processed in BFS manner. Every neighbor is explored and added to the queue if it's not visited, aggregating the fish count for that component.
C++
Java
Python
C#
JavaScript
Time Complexity: O(m*n) given the fixed maximum grid size allowing linear traversal.
Space Complexity: O(m*n), to handle the visitation status and queue space.
| Approach | Complexity |
|---|---|
| Depth-First Search (DFS) | Time Complexity: O(m*n), where m and n are the dimensions of the grid. Each cell is visited once. Space Complexity: O(m*n), to store the visited state of each cell. |
| Breadth-First Search (BFS) | Time Complexity: O(m*n) given the fixed maximum grid size allowing linear traversal. Space Complexity: O(m*n), to handle the visitation status and queue space. |
Maximum Number of Fish in a Grid - Leetcode 2658 - Python • NeetCodeIO • 6,207 views views
Watch 9 more video solutions →Practice Maximum Number of Fish in a Grid with our built-in code editor and test cases.
Practice on FleetCode