Leetcode 1020. Number of Enclaves

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.

Depth First Search Approach:-

The problem states that we can move in all four directions (left, top, right, and bottom), which leads us to model the problem as a graph.

We can treat the 2D grid as an undirected graph. A land cell in grid corresponds to a node in such a graph with an undirected edge between horizontally or vertically adjacent land cells.

If we begin to traverse in this graph from the nodes that are land cells on the boundary and keep on traversing as long as we can, we will visit all the land cells from which we can reach the boundary.

The land cells which aren't visited will be the ones from which we cannot reach the boundary in any way. The count of all these unvisited land cells would be our answer.

We can use a graph traversal algorithm like depth-first search (DFS) to traverse over the land cells.

In DFS, we use a recursive function to explore nodes as far as possible along each branch.

Upon reaching the end of a branch, we backtrack to the previous node and continue exploring the next branches.

Once we encounter an unvisited node, we will take one of its neighbor nodes (if exists) as the next node on this branch.

Recursively call the function to take the next node as the 'starting node' and solve the subproblem.

We perform a DFS from every unvisited land cell at the boundary, treating it as a node.

We traverse all the nodes that are present in the connected component of the starting node and mark them as visited.

After the completion of DFS traversal, we count the number of land cells that are not visited.

    
        class Solution {
            public void dfsUtility(int x, int y, int m, int n, int[][] grid, boolean[][] visited) {
                if (x < 0 || x >= m || y < 0 || y >= n || grid[x][y] == 0 || visited[x][y]) {
                    return;
                }
        
                visited[x][y] = true;
                int[] direction_x = {0, 1, 0, -1};
                int[] direction_y = {-1, 0, 1, 0};
        
                for (int i = 0; i < 4; i++) {
                    dfsUtility(x + direction_x[i], y + direction_y[i], m, n, grid, visited);
                }
                return;
            }
        
            public int numEnclaves(int[][] grid) {
                int m = grid.length;
                int n = grid[0].length;
                boolean[][] visited = new boolean[m][n];
        
                for (int i = 0; i < m; ++i) {
                    // First column.
                    if (grid[i][0] == 1 && !visited[i][0]) {
                        dfsUtility(i, 0, m, n, grid, visited);
                    }
                    // Last column.
                    if (grid[i][n - 1] == 1 && !visited[i][n - 1]) {
                        dfsUtility(i, n - 1, m, n, grid, visited);
                    }
                }
        
                for (int i = 0; i < n; ++i) {
                    // First row.
                    if (grid[0][i] == 1 && !visited[0][i]) {
                        dfsUtility(0, i, m, n, grid, visited);
                    }
                    // Last row.
                    if (grid[m - 1][i] == 1 && !visited[m - 1][i]) {
                        dfsUtility(m - 1, i, m, n, grid, visited);
                    }
                }
        
                int no_of_land_cells = 0;
                for (int i = 0; i < m; i++) {
                    for (int j = 0; j < n; j++) {
                        if (grid[i][j] == 1 && !visited[i][j]) {
                            no_of_land_cells++;
                        }
                    }
                }
                return no_of_land_cells;
            }
        }
    

Complexity Analysis

Time Complexity: O(N+M), where N is a number of nodes (vertices) and M is a number of edges. Space Complexity: O(N). This space is occupied by the visited hash map and in addition to that, space would also be occupied by the recursion stack since we are adopting a recursive approach here.

The space occupied by the recursion stack would be equal to O(H) where H is the height of the graph. Overall, the space complexity would be O(N).