class Solution { public int numEnclaves(int[][] grid) { /* Q2 of graph playlist , we fire GCC from boundary elements and make all 1's in those components as 0 , then we count left no. of 1's in the grid as those are the land cell which will not lead to boundary */ //firing DFS to find components from boundary elements and making them 0 int m = grid.length , n = grid[0].length; for(int i = 0 ;i < m ; i++){ for(int j = 0 ; j< n ; j++){ if(i == 0 || i == m-1 || j == 0 || j == n-1){ if(grid[i][j] == 1) dfs(grid , i , j , m , n); } } } // count no. of land cells and return them int count = 0; for(int i = 0 ;i < m ; i++){ for(int j = 0 ; j< n ; j++){ if(grid[i][j] == 1) count++; } } return count; } int[][] dir = {{0,1},{1,0},{0,-1},{-1,0}}; public void dfs (int[][] grid , int row , int col , int m , int n){ //base case if(row < 0 || col < 0 || row >= m || col >= n || grid[row][col] == 0) return; //making component's 1 to 0 grid[row][col] = 0; for(int i =0 ;i < 4 ; i++) dfs(grid , row + dir[i][0] , col + dir[i][1] , m ,n); } }
Preview:
downloadDownload PNG
downloadDownload JPEG
downloadDownload SVG
Tip: You can change the style, width & colours of the snippet with the inspect tool before clicking Download!
Click to optimize width for Twitter