# 7 lines Python, ~14 lines Java

• Sink and count the islands.

Python Solution

``````def numIslands(self, grid):
def sink(i, j):
if 0 <= i < len(grid) and 0 <= j < len(grid[i]) and grid[i][j] == '1':
grid[i][j] = '0'
map(sink, (i+1, i-1, i, i), (j, j, j+1, j-1))
return 1
return 0
return sum(sink(i, j) for i in range(len(grid)) for j in range(len(grid[i])))
``````

Java Solution 1

``````public class Solution {
char[][] g;
public int numIslands(char[][] grid) {
int islands = 0;
g = grid;
for (int i=0; i<g.length; i++)
for (int j=0; j<g[i].length; j++)
islands += sink(i, j);
return islands;
}
int sink(int i, int j) {
if (i < 0 || i == g.length || j < 0 || j == g[i].length || g[i][j] == '0')
return 0;
g[i][j] = '0';
sink(i+1, j); sink(i-1, j); sink(i, j+1); sink(i, j-1);
return 1;
}
}
``````

Java Solution 2

``````public class Solution {
public int numIslands(char[][] grid) {
int islands = 0;
for (int i=0; i<grid.length; i++)
for (int j=0; j<grid[i].length; j++)
islands += sink(grid, i, j);
return islands;
}
int sink(char[][] grid, int i, int j) {
if (i < 0 || i == grid.length || j < 0 || j == grid[i].length || grid[i][j] == '0')
return 0;
grid[i][j] = '0';
for (int k=0; k<4; k++)
sink(grid, i+d[k], j+d[k+1]);
return 1;
}
int[] d = {0, 1, 0, -1, 0};
}``````

• I like your use of `map`. Great work.

Something I'm confused about is your use of string assignment for python. In the line containing `grid[i][j] = '0'`, you're assigning the `j`th character of string `i` the value `0`, but python doesn't support string assignment. How are you getting past this?

(Your solution works for me, by the way. Maybe it's a flaw within leetcode?)

• Yeah, that `map` usage is a bit of an abuse, but I do like it :-). And it would be great if we didn't have to just count the islands but report their sizes, then `return 1 + sum(map(...))` would be quite nice. And in Python 3 it would even be the perfect way to do it.

You're right, I can't modify strings. But the argument is specified to be `character[][]`, which I guess ends up being a list of lists of one-character strings rather than a list of strings.

• This post is deleted!

• The test cases are given as list of strings, such as ["1011011"]. Probably OJ internally converts them to list of list.

• wow, perfect demonstration for learning how to use map!! It makes code so much simpler!

• ....every time I saw this guy's python I learned something new

• Python solution can be further condensed to:

``````def numIslands(self, grid):
def sink(i, j):
if 0 <= i < len(grid) and 0<= j < len(grid[0]) and grid[i][j] == '1':
grid[i][j] = '0'
map(sink, (i-1, i, i+1, i), (j, j-1, j, j+1) )
return sum(grid[i][j] == '1' and not sink(i,j) \
for i in range(len(grid)) for j in range(len(grid[0])))
``````

• Counting just on the outside... I like it. Having `sink` return 0 or 1 always felt odd because the recursive calls don't use it. But yeah, duplicating the `== '1'` test and the `and not` trick aren't very pretty (not that I don't occasionally do that myself :-)

• The first Python solution is awesome!

• map(sink, (i+1, i-1, i, i), (j, j, j+1, j-1))
Nice!

• Man, you've blown my mind once again!, with the map(sink, (i+1, i-1, i, i), (j, j, j+1, j-1)) hack.

• I have a question here, why do you need the line " g[i][j] = '0';" here? does g[i][j] already equal to zero due to your base condition for sink?

• @mxmingya g[i][j] = '0' to mark the checked cells already, otherwise it would be a forever loop.

• @Pumpkin78 thanks

• I remember str in Python doesn't support item assignment.
Why grid[i][j] = '0' can run successfully?

• @doraemon1293 Because `grid` is a list of lists.

• @StefanPochmann Thx. I saw the test case and thought it is a list of strings.

• grid

Hi Stefan, I try you code but can not pass test case ["1","1"]. It's wired...

• @new2500 You made some mistake, my solutions handle that case correctly.

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