Simple Java Solution


  • 49
    public class NumberofIslands {
    	static int[] dx = {-1,0,0,1};
    	static int[] dy = {0,1,-1,0};
    	public static int numIslands(char[][] grid) {
    		if(grid==null || grid.length==0) return 0;
    		int islands = 0;
    		for(int i=0;i<grid.length;i++) {
    			for(int j=0;j<grid[i].length;j++) {
    				if(grid[i][j]=='1') {
    					explore(grid,i,j);
    					islands++;
    				}
    			}
    		}
    		return islands;
    	}
    	public static void explore(char[][] grid, int i, int j) {
    		grid[i][j]='x';
    		for(int d=0;d<dx.length;d++) {
    			if(i+dy[d]<grid.length && i+dy[d]>=0 && j+dx[d]<grid[0].length && j+dx[d]>=0 && grid[i+dy[d]][j+dx[d]]=='1') {
    				explore(grid,i+dy[d],j+dx[d]);
    			}
    		}
    	}
    }
    

    The algorithm works as follow:

    1. Scan each cell in the grid.
    2. If the cell value is '1' explore that island.
    3. Mark the explored island cells with 'x'.
    4. Once finished exploring that island, increment islands counter.

    The arrays dx[], dy[] store the possible moves from the current cell. Two land cells ['1'] are considered from the same island if they are horizontally or vertically adjacent (possible moves (-1,0),(0,1),(0,-1),(1,0)). Two '1' diagonally adjacent are not considered from the same island.


  • 1
    I

    Well. DFS also costs stack space...
    The space will also be O(n).


  • 0
    N

    your solution is far more clear than mine , and it's helpful , thanks !


  • -17
    S

    Nice and clean solution!
    But I wonder if there could be O(1) solutions for this problem, anyone can give a hint?


  • 0

    Thanks! glad that it helps!


  • 1

    I dont' think you can achieve constant complexity in this problem steven...if you think about the problem you can see that to count the total number of islands you need at least scan all the matrix, so the minimum number of steps will be m*n where m and n are the dimensions of the matrix, anyway if you find better solutions to the problem please share! :)


  • 0
    J

    I think in explore function, it is better to check the condition first. Because in this style, you will put something out of the boundary an 'x'. Is that right?


  • 0

    The explore function will be called only if the value at the corresponding indexes is '1',
    check the condition:

    grid[i][j]=='1'

    in the main function and the condition:

    grid[i+dy[d]][j+dx[d]]=='1'

    before the recursive call


  • 33

    Liked your sharing!
    We have the same idea in this question.
    Just make the island disappear once a cell was found!

    public class Solution {
        public int numIslands(char[][] grid) {
            int count = 0;
            for(int i = 0; i < grid.length; i++){
                for(int j = 0; j < grid[i].length; j++){
                    /*find a cell belong to an island, then disappear the whole 
                      island and increase count*/
                    if(grid[i][j] == '1'){
                        disappear(i,j,grid);
                        count++;
                    }
                }
            }
            return count;
        }
        
        //Use for disapearing an island
        public void disappear(int i, int j, char[][] grid){
            //array edge detect
            if(i < 0 || i >= grid.length){
                return;
            }
            if(j < 0 || j >= grid[i].length){
                return;
            }
            //island edge detect
            if(grid[i][j] == '0'){
                return;
            }
            
            //disapear this cell
            grid[i][j] = '0';
            //disapear other cell in the same island
            disappear(i + 1, j, grid);
            disappear(i - 1, j, grid);
            disappear(i, j + 1, grid);
            disappear(i, j - 1, grid);
        }
    }

  • 0
    W
    This post is deleted!

  • 1
    S

    question: what is the big-O of this algorithm?


  • 0
    M

    Any idea about the upper bound complexity of this one?


  • 0
    F

    Here is my Python version of your code, accepted, thanks for zhang38's hint.

    class Solution(object):
        def numIslands(self, grid):
            """
            :type grid: List[List[str]]
            :rtype: int
            """
            count = 0
            i=0
            j=0
            for i in range(len(grid)):
                for j in range(len(grid[i])):
                    if grid[i][j]== '1':
                        self.sink(i,j,grid)
                        count+=1
            return count
            
        def sink(self,i,j,grid):
            #border check:
            if i<0 or i>=len(grid):return
            if j<0 or j>=len(grid[i]):return
        
            if grid[i][j]=='0': return
            
            #sink this cell
            grid[i][j]='0'            
            
            self.sink(i+1,j,grid)
            self.sink(i-1,j,grid)
            self.sink(i,j+1,grid)
            self.sink(i,j-1,grid)

  • 0
    Z

    because you forget to change the mark in your sink method


  • 0
    F

    Great, my bad, thanks! Updated my AC code as well.


  • 0
    Z

    There is no need to set visited cells as 'x', just to set them as '0' is fine.


  • 0
    L

    I love your solution. really easy to understand


  • 1

    Thanks for your comment.


  • 0
    P

    thanks for sharing. could you analyze the complexity of the python version?


  • 0
    K

    @zwangbo said in Simple Java Solution:

    disapear other cell in the same island

    Could you pls explain the disappear part. What is it meant for? Thanks


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.