algoadvance

Leetcode 695. Max Area of Island

Problem Statement

Given a non-empty 2D array grid of 0’s and 1’s, 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.

Find the maximum area of an island in the given 2D array. If there is no island, return 0.

Clarifying Questions

1. Can the grid be non-rectangular?
   • No, the grid is rectangular.
2. What are the constraints on the size of the grid?
   • The size of the grid is m x n where 1 <= m, n <= 50.
3. Are there any other elements apart from 0 and 1 in the grid?
   • No, the grid only contains 0’s and 1’s.
4. Is diagonal connection considered as part of the same island?
   • No, only horizontal and vertical connections are considered. Diagonals are not part of the same island.

Strategy

1. Traversal and DFS/BFS Approach: Traverse every cell in the grid. If a cell contains a 1, perform a Depth First Search (DFS) or Breadth First Search (BFS) to calculate the area of the island connected to that cell.
2. Mark Visited Cells: As you explore cells connected to the initial cell using DFS/BFS, mark them as visited by changing their value to 0, to avoid counting them multiple times.
3. Update Max Area: Keep track of the maximum area encountered during the traversal.

Code

public class Solution {
    public int maxAreaOfIsland(int[][] grid) {
        int maxArea = 0;
        // Dimensions of the grid
        int rows = grid.length;
        int cols = grid[0].length;

        // Iterate through every cell in the grid
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] == 1) {
                    // Calculate the area of the island using DFS or BFS
                    int area = dfs(grid, r, c);
                    // Update the maximum area found so far
                    maxArea = Math.max(maxArea, area);
                }
            }
        }
        return maxArea;
    }

    private int dfs(int[][] grid, int r, int c) {
        // Boundary and base condition checks
        if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length || grid[r][c] == 0) {
            return 0;
        }
        
        // Mark the cell as visited by setting it to 0
        grid[r][c] = 0;
        int area = 1; // Counting the current cell

        // Explore all four possible directions
        area += dfs(grid, r + 1, c); // down
        area += dfs(grid, r - 1, c); // up
        area += dfs(grid, r, c + 1); // right
        area += dfs(grid, r, c - 1); // left

        return area;
    }
}

Time Complexity

• Time Complexity: ( O(m \times n) )
  • We potentially visit every cell once, and each visited cell triggers a DFS which also operates within ( O(m \times n) ) time.
• Space Complexity: ( O(m \times n) )
  • The space complexity is primarily due to the recursion stack in the worst case where the grid is entirely land, causing a recursion depth of ( m \times n ).

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?