463. Island Perimeter

def island_perimeter(grid):
    """Naive answer
    Time Complexity: O(nm)
    Space Complexity: O(1)
    """
    def edges(i, j):
        nonlocal rows, cols
        up = 1 if i > 0 and grid[i-1][j] == 1 else 0          # actually not needed
        down = 1 if i < rows-1 and grid[i+1][j] == 1 else 0
        left = 1 if j > 0 and grid[i][j-1] == 1 else 0        # actually not needed
        right = 1 if j < cols-1 and grid[i][j+1] == 1 else 0
        return 4 - up - down - left - right

    rows, cols = len(grid), len(grid[0])
    perimeter = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 1:
                perimeter += edges(r, c)
    return perimeter

def island_perimeter(grid):
    """similar as above but with a bit of optimization
    Time Complexity: O(nm)
    Space Complexity: O(1)
    """
    def edges(i, j):
        nonlocal rows, cols
        down = 2 if i < rows-1 and grid[i+1][j] == 1 else 0    # only those have not been counted
        right = 2 if j < cols-1 and grid[i][j+1] == 1 else 0   # by previous iteration of edges(r, c)
        return 4 - down - right
    
    rows, cols = len(grid), len(grid[0])
    perimeter = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 1:
                perimeter += edges(r,c)
    return perimeter

def island_perimeter(grid):
    """similar but with Space Complexity: O(nm)"""
    rows = len(grid)
    cols = len(grid[0])
    extended_grid = [[0]*(cols+2)] + [[0]+row+[0] for row in grid] + [[0]*(cols+2)]
    perimeter = 0

    for i in range(rows+1):
        for j in range(cols+1):
            if extended_grid[i][j] != extended_grid[i][j+1]:
                # land | sea  or  sea | land
                perimeter += 1
            if extended_grid[i][j] != extended_grid[i+1][j]:
                #   sea             land       
                #  ------    or    ------      
                #  land             sea       
                perimeter += 1

    return perimeter

def island_perimeter(grid):
    """by zipping rows together and columns together
    
         [[a, b, c, d],                             [(a,a,a,a,a),
          [a, b, c, d],                              (b,b,b,b,b),
    MAT = [a, b, c, d],  -->  zip(*MAT) = zip object (c,c,c,c,c), 
          [a, b, c, d],                              (d,d,d,d,d)]
          [a, b, c, d]]
    """

    # convert each row into a string: '0+i[0]i[1]i[2]...i[n]+0' and store it as a list in grid_r
    grid_r = ['0' + ''.join(str(r) for r in row) + '0' for row in grid]  
    # convert each column into a string: '0+j[0]j[1]j[2]...j[n]+0'' and store it as a list in grid_c
    grid_c = ['0' + ''.join(str(c) for c in col) + '0' for col in zip(*grid)]
    
    return sum(row.count('01') + row.count('10') for row in grid_r + grid_c)
    # grid_r + grid_c means that it will first check grid_r and then grid_c 

    #               '01'               |              '10'
    # ---------------------------------|---------------------------------
    #     grid_r      |     grid_c     |    grid_r      |     grid_c     
    # ----------------|----------------|----------------|------------------
    #                 |     sea        |                |     land       
    #   sea | land    |    ------      |   land | sea   |    ------      
    #                 |     land       |                |     sea       

from itertools import chain

def island_perimeter(grid):
    """Variation of the one just above using zip() but with generator instead of list
    --> more space efficient.
    --> requires chain() to do grid_r + grid_c
    """
    grid_r = ('0' + ''.join(str(r) for r in row) + '0' for row in grid)
    grid_c = ('0'+''.join(str(c) for c in col) + '0' for col in zip(*grid))
    return sum(row.count('01') + row.count('10') for row in chain(grid_r, grid_c))

def island_perimeter(grid):
    perimeter = 0
    for row in grid + list(map(list, zip(*grid))):
        # map(list, zip()) --> convert tuples inside zip into list
        # list(zip) --> convert zip object into list
        for i, j in zip([0] + row, row + [0]):
            if i != j:
                perimeter += 1
    return perimeter

import operator

def island_perimeter(grid):
    """Same as above but in one line
    Note: operator.ne = '!='
    '"""
    return sum(sum(map(operator.ne, [0] + row, row + [0])) for row in grid + list(map(list, zip(*grid))))