algoadvance

Leetcode 695. Max Area of Island

Problem Statement

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.

Clarifying Questions

  1. Input Constraints:
    • What are the constraints on m and n (the dimensions of the grid)?
      • Typically in such problems, m and n could range from 1 to 50 or 1 to 100.
    • Is the grid guaranteed to have at least one cell (i.e., m, n >= 1)?
      • Yes, [m, n] >= 1.
  2. Cell Values:
    • The grid contains only 0s and 1s, correct?
      • Yes.
  3. Edge Cases:
    • What should be returned if there are no 1 values in the grid?
      • Return 0.

Strategy

We’ll use Depth-First Search (DFS) to explore each island and compute its area. Once an island is fully traversed, we will update our maximum area if the current island’s area is larger than the previously recorded maximum.

Steps:

  1. Loop through each cell in the grid.
  2. When a 1 is encountered, perform DFS to find the full extent of the island.
  3. During DFS, mark visited land cells as 0 to avoid revisiting.
  4. Keep track of the count of 1s encountered during the DFS (which gives the area of the island).
  5. Update the maximum area accordingly.
  6. Continue until all cells are checked.

Code

#include <vector>
#include <algorithm>

class Solution {
public:
    int maxAreaOfIsland(std::vector<std::vector<int>>& grid) {
        if (grid.empty() || grid[0].empty()) return 0;
        
        int max_area = 0;
        for (int i = 0; i < grid.size(); i++) {
            for (int j = 0; j < grid[0].size(); j++) {
                if (grid[i][j] == 1) {
                    int area = dfs(grid, i, j);
                    max_area = std::max(max_area, area);
                }
            }
        }
        return max_area;
    }
    
private:
    int dfs(std::vector<std::vector<int>>& grid, int i, int j) {
        if (i < 0 || i >= grid.size() || j < 0 || j >= grid[0].size() || grid[i][j] == 0) {
            return 0;
        }
        
        grid[i][j] = 0; // Mark the cell as visited by changing it to 0
        
        int area = 1;
        area += dfs(grid, i + 1, j);
        area += dfs(grid, i - 1, j);
        area += dfs(grid, i, j + 1);
        area += dfs(grid, i, j - 1);

        return area;
    }
};

Time Complexity

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