7 lines Python, ~14 lines Java


  • 86

    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};
    }

  • 3
    H

    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 jth 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?)


  • 2

    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.


  • 0
    S
    This post is deleted!

  • 0
    S

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


  • 0
    O

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


  • 2
    A

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


  • 3
    T

    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])))
    

    Your original version is more readable though.


  • 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 :-)


  • 0
    C

    The first Python solution is awesome!


  • 0
    F

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


  • 0
    C

    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.


  • 0
    M

    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?


  • 1
    P

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


  • 0
    M

    @Pumpkin78 thanks


  • 0
    D

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


  • 0

    @doraemon1293 Because grid is a list of lists.


  • 0
    D

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


  • 0

    @StefanPochmann said in 7 lines Python, ~14 lines Java:

    grid

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


  • 0

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


Log in to reply
 

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