652. Largest Island Area
A city planner is studying a block map grid with R rows and C columns. A cell holding 1 is a built-up lot and a cell holding 0 is empty ground. Built-up lots that touch along a side (up, down, left or right) belong to the same district; lots that touch only at a corner are in different districts.
Return the area of the largest district, where the area of a district is the number of lots it contains. If the map contains no built-up lot, return 0. The expected solution runs in O(R * C) time with O(R * C) extra space and does not rely on recursion.
Example 1
- Input:
- grid = [[0,1,1,0],[0,1,0,0],[0,0,0,1]]
- Output:
- 3
- Explanation:
The largest district is the three connected lots in the upper part, so the answer is 3.
Example 2
- Input:
- grid = [[1,0,1],[0,1,0],[1,0,1]]
- Output:
- 1
- Explanation:
Lots touching only at corners are separate districts, so the largest has area 1.
Example 3
- Input:
- grid = [[0,0],[0,0],[0,0]]
- Output:
- 0
- Explanation:
There are no lots, so the answer is 0.
Constraints
1 ≤ R, C ≤ 400
grid[i][j] is 0 or 1
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 2,000 msC++ 500 msJava 1,000 msJavaScript 1,000 msTypeScript 1,000 ms
Expected complexity
- Time
- O(R * C)
- Space
- O(R * C)