Skip to main content

1020. Number of Enclaves

https://leetcode.com/problems/number-of-enclaves/

Python​

Mark and Query - DFS​

class Solution:
    def numEnclaves(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])

        def dfs(i, j):
            if i < 0 or i >= m or j < 0 or j >= n:
                return

            if grid[i][j] <= 0:
                return

            grid[i][j] = -1

            for rx, cx in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                dfs(i+rx, j+cx)

        # Mark reachable islands from edges
        for row in range(m):
            dfs(row, 0)
            dfs(row, n-1)

        for col in range(n):
            dfs(0, col)
            dfs(m-1, col)

        # Count the remains islands
        ans = 0
        for row in range(m):
            for col in range(n):
                if grid[row][col] == 1:
                    ans += 1
        return ans

Mark and Query - BFS (Timelimit Exceed)​

from collections import deque


class Solution:
    def numEnclaves(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])

        queue = deque()

        for row in range(m):
            if grid[row][0] == 1:
                queue.append((row, 0))
            if grid[row][n-1] == 1:
                queue.append((row, n-1))

        for col in range(n):
            if grid[0][col] == 1:
                queue.append((0, col))
            if grid[m-1][col] == 1:
                queue.append((m-1, col))

        while queue:
            row, col = queue.popleft()
            grid[row][col] = -1

            for rx, cx in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
                rn, cn = row+rx, col+cx
                if rn >= 0 and rn < m and cn >= 0 and cn < n and grid[rn][cn] == 1:
                    queue.append((rn, cn))

        ans = 0
        for row in range(m):
            for col in range(n):
                if grid[row][col] == 1:
                    ans += 1
        return ans