695. Max Area of Island

Problem

Tags: Array, Depth-First Search, Breadth-First Search, Union Find, Matrix

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.

Example 2:

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.

Code

C

// 695. Max Area of Island (1/8/53956)
// Runtime: 8 ms (94.30%) Memory: 6.88 MB (27.85%) 

int maxAreaOfIsland(int** grid, int gridSize, int* gridColSize) {
    int m = gridSize, n = gridColSize[0];
    
    int find(int x, int y) {
        // 如果是 (x, y) 是海洋或是已經找過了，就不要繼續
        if (grid[y][x] == 0 || grid[y][x] == 2) return 0;

        // area 是這一個陸塊的大小
        int area = 1;

        // 紀錄這塊地已找過
        grid[y][x] = 2;

        // 如果右邊不是邊界，找右邊
        if (x + 1 < n) area += find(x + 1, y);
        // 如果左邊不是邊界，找左邊
        if (x > 0) area += find(x - 1, y);
        // 如果下面不是邊界，找下面
        if (y + 1 < m) area += find(x, y + 1);
        // 如果上面不是邊界，找上面
        if (y > 0) area += find(x, y - 1);

        // 回傳該陸塊總大小
        return area;
    }

    int max = 0;

    // 遍歷所有位置
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            // 如果是陸地，則找該陸地所屬陸塊大小
            if (grid[i][j] == 1) {
                int area = find(j, i);
                max = area > max ? area : max;
            }
        }
    }

    return max;
}

JS

// 695. Max Area of Island (4/19/53388)
// Runtime: 108 ms (50.86%) Memory: 40.80 MB (94.96%) 

/**
 * @param {number[][]} grid
 * @return {number}
 */
var maxAreaOfIsland = function(grid) {
    let max = 0;
    
    const dfs = (i, j) => {
        if (i >= 0 && j >= 0 && i < grid.length && j < grid[i].length && grid[i][j] === 1) {
            grid[i][j] = 0;
            return 1 + dfs(i+1, j) + dfs(i-1, j) + dfs(i, j+1) + dfs(i, j-1);
        } else return 0;
    }
    
    for (let i = 0; i < grid.length; i += 1) {
        for (let j = 0; j < grid[i].length; j += 1) {
            if (grid[i][j] === 1) {
                const area = dfs(i,j);
                max = area > max ? area : max;
            }
        }
    }
    return max;
};