class Solution {
    public int numEnclaves(int[][] grid) {
        int n = grid.length;
        int m = grid[0].length;

        int[][] visited = new int[n][m];

        // step-1 check the boundary characters 
        // traversing through boundary 0th col, last row, last col, 0th row
        for(int i=0; i<n; i++)
        {
            for(int j=0; j<m; j++)
            {
                // 0th col
                if(grid[i][0] == 1 && visited[i][0] != 1)
                {
                    dfs(grid, visited, i, 0, n, m);
                }
                // last col
                else if(grid[i][m-1] == 1 && visited[i][m-1] != 1)
                {
                    dfs(grid, visited, i, m-1, n, m);
                }
                // 0th row
                else if(grid[0][j] == 1 && visited[0][j] != 1)
                {
                    dfs(grid, visited, 0, j, n, m);
                }
                // last row
                else if(grid[n-1][j] == 1 && visited[n-1][j] != 1)
                {
                    dfs(grid, visited, n-1, j, n, m);
                }
            }
        }

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

                // reverting back as we marked 'Y' for temporary purpose
                else if(grid[i][j] == 2)
                    grid[i][j] = 1;
            }
        }
        return countLandCells;
    }

    int[] deltaRow = {-1, 1, 0, 0};
    int[] deltaCol = {0, 0, 1, -1};
    public void dfs(int[][] grid, int[][] visited, int row, int col, int n, int m)
    {
        visited[row][col] = 1;
        // Mark this cell as visited and temporary number as 2 to prevent it from being changed
        // as these are boundary land cells
        grid[row][col] = 2;

        for(int i=0; i<4; i++)
        {
            int nRow = row + deltaRow[i];
            int nCol = col + deltaCol[i];

            if(nRow >= 0 && nCol >= 0 && nRow < n && nCol < m)
            {
                // checking if neighbour cell is land cell
                if(visited[nRow][nCol] == 0 && grid[nRow][nCol] == 1)
                {
                    dfs(grid, visited, nRow, nCol, n, m);
                }
            }
        }
    }
}