Python short & efficient solution with explanation: O(mn) time and O(1) space


  • 8

    My solution from the contest. For each cell with land on it add the number of cells around it that have water. All cells that are not on the grid are considered to have water:

    def islandPerimeter(self, grid):
        def water_around(y, x):
            return ((x == 0              or grid[y][x-1] == 0) +
                    (x == len(grid[0])-1 or grid[y][x+1] == 0) +
                    (y == 0              or grid[y-1][x] == 0) +
                    (y == len(grid)-1    or grid[y+1][x] == 0) )
        return sum(water_around(y, x) for y in xrange(len(grid)) for x in xrange(len(grid[0])) if grid[y][x])
    

    UPDATE: Changed calls to range to use xrange instead. See posts below for further discussion on the effects of this change.


  • 1

    Since LeetCode uses Python 2, you'll need to use xrange for O(1) space. Right now it's Θ(m+n) space. (fixed now)


  • 1

    True, the original code was O(1) space in Python3, but not in Python2.

    Using xrange makes the code non-compatible with Python3, which I find undesirable. I think that the best solution to ensure O(1) space and forward compatibility would be to include the following:

    from six.moves import range
    

    I'm just leaving this as a comment but I'm modifying the code as per your comment, since LeetCode doesn't support the six library.


  • 2

    Oh, actually you could use enumerate in both Python versions:

    return sum(water_around(y, x) for y, row in enumerate(grid) for x, cell in enumerate(row) if cell)
    

    It's even one byte shorter than your original with range :-)


  • 0
    L
    This post is deleted!

  • 1
    M

    It is indeed short but may not be very efficient:
    if the island has a lot of inland cells, a lot of edges are counted twice.

    The ideal case for your algorithm is a 1-cell island, in which no edges are doubly counted.
    The worst case for your algorithm is a full-grid island, in which almost all edges are doubly counted.

    P.S. That's my first solution as well, although not coded as neatly as how you brilliantly did.


Log in to reply
 

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