1002 Number of Enclaves

Techniques Used

• Graph
• Simple DFS

Similar Problem

• 1254 Number of Closed Islands

Approach

• Apply dfs on the boundary elements which are 1's, and "sink" them to '0'. (make all the 1's connected 4-directionally to boundary 1's as 0).
• Loop over the grid again, and count the remaining 1's.

Complexity:

• Time Complexity: O(mn)
• Space Complexity: O(1)

Code:

class Solution {
    public int numEnclaves(int[][] grid) {

        int m = grid.length;
        int n = grid[0].length;

        int count = 0;


        for(int i =  0; i < m; i++){
            for(int j =  0; j < n; j++){
                if(i == 0 || j == 0 || i == m - 1 || j == n - 1){

                    dfs(grid, i, j);


                }

            }
        }



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

        return count;

    }

    static void dfs(int[][] grid, int row, int col){


        if(row < 0 || col < 0 || row >= grid.length || col >= grid[0].length || grid[row][col] == 0){
            return;
        }


        grid[row][col] = 0;

        dfs(grid, row - 1, col);
        dfs(grid, row + 1, col);
        dfs(grid, row, col  + 1);
        dfs(grid, row, col - 1);

        return;

    }

}