LC-0695 Medium LeetCode

695. Max Area of Island

Array Depth-First Search Breadth-First Search Union Find Matrix

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 73% Topics: Array, Depth-First Search, Breadth-First Search, Union Find, Matrix

Reading material

Arrays & Hashing 12 min Trees & Traversals 18 min Union–Find (DSU) 12 min

Reference solution (spoiler · python)

# Time:  O(m * n)
# Space: O(m * n), the max depth of dfs may be m * n

class Solution(object):
    def maxAreaOfIsland(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        directions = [[-1,  0], [ 1,  0], [ 0,  1], [ 0, -1]]

        def dfs(i, j, grid, area):
            if not (0 <= i < len(grid) and \
                    0 <= j < len(grid[0]) and \
                    grid[i][j] > 0):
                return False
            grid[i][j] *= -1
            area[0] += 1
            for d in directions:
                dfs(i+d[0], j+d[1], grid, area)
            return True

        result = 0
        for i in xrange(len(grid)):
            for j in xrange(len(grid[0])):
                area = [0]
                if dfs(i, j, grid, area):
                    result = max(result, area[0])
        return result

Solution from kamyu104/LeetCode-Solutions · MIT