class Solution { public int numIslands(char[][] grid) { /* we treat this like a question of graph to find components which are islands in this case */ boolean visited[][] = new boolean [grid.length][grid[0].length]; int component = 0; //dfs from every node for(int i = 0 ; i < grid.length ;i++){ for(int j = 0 ; j < grid[0].length ;j++){ //if it is land and visited is false if(grid[i][j] == '1' && visited[i][j] == false){ dfs(grid , i , j , visited); component++; } } } return component; } public void dfs (char[][]grid , int i , int j , boolean[][] visited){ //base case if(i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || visited[i][j] == true || grid[i][j] == '0') return ; visited[i][j] = true; //going in all 4 directions dfs(grid , i , j+1 , visited); dfs(grid , i+1 , j , visited); dfs(grid , i-1 , j , visited); dfs(grid , i , j-1 , visited); } }
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