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)-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)) 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.
Since LeetCode uses Python 2, you'll need to use (fixed now)
xrange for O(1) space. Right now it's Θ(m+n) space.
True, the original code was O(1) space in Python3, but not in Python2.
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.
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
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.
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.