Short Python


  • 52

    Since there are no lakes, every pair of neighbour cells with different values is part of the perimeter (more precisely, the edge between them is). So just count the differing pairs, both horizontally and vertically (for the latter I simply transpose the grid).

    def islandPerimeter(self, grid):
        return sum(sum(map(operator.ne, [0] + row, row + [0]))
                   for row in grid + map(list, zip(*grid)))

  • 0
    R

    Hi @StefanPochmann - Thanks for your solution, but could you elaborate on your idea? What do you mean by "every pair of connected cells with different values is part of the perimeter"? Thanks a lot!


  • 2

    @tw_arthur If you have a water cell next to a land cell, then they (more precisely the edge between them) is part of the perimeter. I rewrote it a bit, hopefully it's clearer now.


  • 0
    R

    this is an awesome idea! Now I understand your usage of map(operator.ne, [0] + row, row + [0]).


  • 0
    S

    Clever solution!


  • 1
    F

    short in python, but long in java, the same idea:

        public int islandPerimeter(int[][] grid) {
            int m = grid.length;
            int n = grid[0].length;
            int result = 0;
            for (int[] aGrid : grid) {
                if (aGrid[0] == 1) {
                    result++;
                }
                for (int i = 1; i < n; i++) {
                    if (aGrid[i - 1] != aGrid[i]) {
                        result++;
                    }
                }
                if (aGrid[n - 1] == 1) {
                    result++;
                }
            }
            for (int j = 0; j < n; j++) {
                if (grid[0][j] == 1) {
                    result++;
                }
                for (int i = 1; i < m; i++) {
                    if (grid[i - 1][j] != grid[i][j]) {
                        result++;
                    }
                }
                if (grid[m - 1][j] == 1) {
                    result++;
                }
            }
            return result;
        }
    

  • 2
    S

    For python 3.5.1, I had to convert map to a list before concatenation for transpose (last line):

    for row in grid + list(map(list, zip(*grid))))
    

    Alternatively:

    for row in grid + [list(x) for x in zip(*grid)])
    

  • 0
    S

    @sanket.purbey
    this will do
    for row in list(zip(*grid))


  • 1
    S

    @StefanPochmann
    awesome idea!

    can you explain how the following line will work to count the edges in each row?

    map(operator.ne, [0] + row, row + [0])


  • 0

    @StevenYU

    Lets take an example:

    [0] + [1,2,3,4,5,6,7,8] = [0,1,2,3,4,5,6,7,8]
    [1,2,3,4,5,6,7,8] + [0] = [1,2,3,4,5,6,7,8,0]

    basically, operator.ne compares 1 with 0 and 2, and compares 2 with 1 and 3...... It compares every element with its two neighbors.

    Hope it helps!


  • 0
    A

    I would be appreciated if who can explain the following code for me:

    for row in grid + map(list, zip(*grid)))
    

  • 0
    D

    @azxx First, for row in... is list comprehension a generator expression, where row is a row or column of the map. Second, the + map(list, zip(*grid))) is appending the transposition of the map, so columns become rows. The resulting extended grid looks like

    [0, 1, 0, 0]
    [1, 1, 1, 0]
    [0, 1, 0, 0]
    [1, 1, 0, 0]
    [0, 1, 0, 1]
    [1, 1, 1, 1]
    [0, 1, 0, 0]
    [0, 0, 0, 0]
    .

    Edits thanks to @ManuelP


  • 5
    Y

    A straightforward implementation of your idea is:

    class Solution(object):
        def islandPerimeter(self, grid):
            grid_ext = ['0' + ''.join(str(x) for x in row) + '0' for row in grid]
            grid_trans = list(map(list, zip(*grid)))
            grid_ext += [ '0' + ''.join(str(x) for x in row) + '0' for row in grid_trans ]                
            return sum(row.count('01') + row.count('10') for row in grid_ext)
    

    And, this version is somewhat like your solution to the TotalHammingDistance: https://discuss.leetcode.com/topic/72149/python-via-strings


  • 0
    P

    @ysonglc Thank for your explanation, it makes me more clear about the codes.


  • 0
    X

    Great, very good solution !


  • 0
    Y

    awesome solution!


  • 0
    A

    Awesome solution.


  • 0
    C

    @StefanPochmann said in Short Python:
    Thanks a lot for sharing this incredibly short solution!
    A quick question, how does having lakes make your solution not valid? your solution seems to work for the case where we have lakes too. Im just trying to understand what piece of information the problem description is giving us when it specifies that "(...) the island doesn't have lakes (...)"


  • 0

    @carconper Well I'd say lakes would be part of the island and thus not affect its perimeter. But they'd affect the value I calculate.


  • 0
    C

    @StefanPochmann You are right. Edges of a lake wouldn't be considered as the perimeter of the island. Thanks!


Log in to reply
 

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