Problem of The Day: Insert into a Binary Search Tree

Problem Statement

leetcode problem link

DFS Iterative Approach [Accepted]

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        res = 0
        ROWS = len(grid)
        COLS = len(grid[0])
        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        seen = set()

        def valid(row, col):
            return 0 <= row < ROWS and 0 <= col < COLS and grid[row][col] == 1

        def dfs(r, c):
            ans = 1
            stack = [(r, c)]
            seen.add((r, c))
            while stack:
                row, col = stack.pop()

                for x, y in directions:
                    next_row, next_col = row + x, col + y
                    if valid(next_row, next_col) and (next_row, next_col) not in seen:
                        stack.append((next_row, next_col))
                        seen.add((next_row, next_col))
                        ans += 1

            return ans


        for row in range(ROWS):
            for col in range(COLS):
                if grid[row][col] == 1 and (row, col) not in seen:
                    res = max(res, dfs(row, col))

        return res

Editorial

Approach #1: Depth-First Search (Recursive) [Accepted]

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(r-1, c) +
                    area(r, c-1) + area(r, c+1))

        return max(area(r, c)
                   for r in range(len(grid))
                   for c in range(len(grid[0])))

Approach #2: Depth-First Search (Iterative) [Accepted]

class Solution(object):
    def maxAreaOfIsland(self, grid):
        seen = set()
        ans = 0
        for r0, row in enumerate(grid):
            for c0, val in enumerate(row):
                if val and (r0, c0) not in seen:
                    shape = 0
                    stack = [(r0, c0)]
                    seen.add((r0, c0))
                    while stack:
                        r, c = stack.pop()
                        shape += 1
                        for nr, nc in ((r-1, c), (r+1, c), (r, c-1), (r, c+1)):
                            if (0 <= nr < len(grid) and 0 <= nc < len(grid[0])
                                    and grid[nr][nc] and (nr, nc) not in seen):
                                stack.append((nr, nc))
                                seen.add((nr, nc))
                    ans = max(ans, shape)
        return ans