Max Area of Island (Leetcode 695)

Difficulty: Medium Link: Day1 : June LeetCode Challenge

Problem Description

You are given an m x n binary matrix grid. An island is a group of 1‘s (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.

The area of an island is the number of cells with a value 1 in the island.

Return the maximum area of an island in grid. If there is no island, return 0.

Example 1:

Input: grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]
Output: 6
Explanation: The answer is not 11, because the island must be connected 4-directionally.
Input: grid = [[0,0,0,0,0,0,0,0]]
Output: 0

Constraints

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 50
  • grid[i][j] is either 0 or 1.

Solution

We want to find out the maximum area in the grid. A cell would contribute to the area if it is a land (grid[i][j] = 1 )otherwise it is water. Whenever we come on the land, we can explore all the 4 directions to find the connected cells. The total area would be the sum of all such connected cells.

Depth First Search

This is the best technique to traverse any 2D grid if we want to maximise the extant of any quantity (number of continuous cells in this case). We can process the input grid using nested loops and recursively call the dfs whenever we are on the land. The dfs procedure would in-turn recursively check for all the 4 directions and return the total of land cells.

Trick case

There are chances of infinite loop since we are blindly traversing all the 4 directions and we would revisit some cells again which in-turn would trigger the recursion all over again. For ex, image two 1 connected together. They would keep on calling to their neighbours infinitely. To handle this case, whenever before recursively exploring the 4 directions, we will set the input grid at that cell = 0, so that it does not get counted again.

Swift

class Solution {
func maxAreaOfIsland(_ grid: [[Int]]) -> Int {
var maxArea = 0 , grid = grid
for i in 0..<grid.count{
for j in 0..<grid[0].count{
if grid[i][j] == 0 {
continue
}
let area = dfs(i,j,&grid)
maxArea = max(area,maxArea)
}
}
return maxArea
}
func dfs(_ row:Int,_ col:Int, _ board:inout [[Int]]) -> Int {
guard row >= 0 , row < board.count, col >= 0, col < board[0].count else { return 0}
if board[row][col] == 0 { return 0}
board[row][col] = 0
var count = 1 // Self
count += dfs(row+1,col,&board) + dfs(row1,col,&board) // Down, Up
count += dfs(row,col+1,&board) + dfs(row,col1,&board) // Right , Left
return count
}
}

Python

class Solution(object):
def maxAreaOfIsland(self, grid):
seen = set()
def area(r, c):
if not (0 <= r < len(grid) and 0 <= c < len(grid[0])
and (r, c) not in seen and grid[r][c]):
return 0
seen.add((r, c))
return (1 + area(r+1, c) + area(r1, c) +
area(r, c1) + area(r, c+1))
return max(area(r, c)
for r in range(len(grid))
for c in range(len(grid[0])))
view raw max_area_island.py hosted with ❤ by GitHub

Java

class Solution {
int[][] grid;
boolean[][] seen;
public int area(int r, int c) {
if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length ||
seen[r][c] || grid[r][c] == 0)
return 0;
seen[r][c] = true;
return (1 + area(r+1, c) + area(r1, c)
+ area(r, c1) + area(r, c+1));
}
public int maxAreaOfIsland(int[][] grid) {
this.grid = grid;
seen = new boolean[grid.length][grid[0].length];
int ans = 0;
for (int r = 0; r < grid.length; r++) {
for (int c = 0; c < grid[0].length; c++) {
ans = Math.max(ans, area(r, c));
}
}
return ans;
}
}

Complexity Analysis

  • Time = O(RC), where R is the number of rows in the given grid, and C is the number of columns. We visit every square once.
  • Space = O(R∗C), the space used by the call stack during our recursion.

Leave a Reply

Your email address will not be published. Required fields are marked *