Number of Enclaves

Leetcode Daily Challenge (7th April, 2023)

7 April, 2023

Contributors

Lakshit Chiranjiv Sagar

@lakshit-cs

Problem Statement:-

You are given an m x n binary matrix grid, where 0 represents a sea cell and 1 represents a land cell.

A move consists of walking from one land cell to another adjacent (4-directionally) land cell or walking off the boundary of the grid.

Return the number of land cells in grid for which we cannot walk off the boundary of the grid in any number of moves.

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

Problem Explanation with examples:-

Example 1

Input: grid = [[0,1,1,0],[0,0,1,0],[0,0,1,0],[0,0,0,0]]
Output: 0
Explanation: All 1s are either on the boundary or can reach the boundary.

Example 2

Input: grid = [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]
Output: 3
Explanation: There are three 1s that are enclosed by 0s, and one 1 that is not enclosed because its on the boundary.

Constraints

1 <= grid.length, grid[0].length <= 100
0 <= grid[i][j] <=1

Intuition:-

We start from the boundaries of the grid and call dfs on all the 1s. We mark all the 1s that are connected to the boundaries as -1.
We then count the number of 1s that are not marked as -1 and return it as those 1s are not reachable from the boundaries.

Solution:-

Initialize m to the number of rows in the grid and n to the number of columns in the grid
Initialize count to 0.
Define dfs as follows:
If the cell is out of bounds or the cell is not 1, then we return.
Else, we mark the cell as -1 and call dfs on the 4 adjacent cells.
After the dfs function, for each boundary row, we call dfs on the first and last column.
For each boundary column, we call dfs on the first and last row.
For each cell in the grid, if the cell is 1, then we increment count by 1.
Return count at the end.

Code:-

JAVA Solution

public class Solution {
    public int numEnclaves(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int count = 0;
        
        void dfs(int i, int j) {
            if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] != 1) {
                return;
            }
            
            grid[i][j] = -1;
            dfs(i - 1, j);
            dfs(i + 1, j);
            dfs(i, j - 1);
            dfs(i, j + 1);
        }

        for (int i = 0; i < m; i++) {
            dfs(i, 0);
            dfs(i, n - 1);
        }

        for (int j = 0; j < n; j++) {
            dfs(0, j);
            dfs(m - 1, j);
        }
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    count++;
                }
            }
        }
        return count;
    }
}

Python Solution

class Solution:
    def numEnclaves(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        count = 0
        
        def dfs(i, j):
            if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] != 1:
                return
            
            grid[i][j] = -1
            dfs(i - 1, j)
            dfs(i + 1, j)
            dfs(i, j - 1)
            dfs(i, j + 1)

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

        for j in range(n):
            dfs(0,j)
            dfs(m-1,j)
        
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    count += 1
        return count

Complexity Analysis:-

TIME:-

The time complexity is O(m * n) where m is the number of rows in the grid and n is the number of columns in the grid. The solution performs a depth-first search (DFS) on all the boundary cells of the grid and then iterates over the entire grid to count the remaining 1's. Thus, the time complexity is O(m*n).

SPACE:-

The space complexity is O(m * n) where m is the number of rows in the grid and n is the number of columns in the grid since the solution modifies the input grid in place and uses a recursive stack to perform the DFS.

References:-

DFS

Connect with me:-

java

python

leetcode

dsa