[Moderate] interview questions #19

[rygh4775]

Pond Sizes: You have an integer matrix representing a plot of land, where the value at that location represents the height above sea level. A value of zero indicates water. A pond is a region of water connected vertically, horizontally, or diagonally. The size of the pond is the total number of connected water cells. Write a method to compute the sizes of all ponds in the matrix. EXAMPLE Input: o 2 1 a a 1 a 1 1 1 a 1 o 1 0 1 Output: 2, 4, 1 (in any order)

[RoyMoon]

Solution :

1. find a pond
2. measure a size of pond and flagging visited land

def computePondSizes() :
    row = len(land)
    col = len(land[0])
    #print( row ," : " , col)

    for r in range(row) :
        for c in range(col):
            if isVisited(r,c) == False and land[r][c] == 0:
                size = computeSize(r,c)

                if size != 0 :
                    print(size)

def isVisited(row ,col):
    if visited[row][col] != 0 :
        return True
    return False

def isValid(row ,col) :
    if row < 0 or col < 0 or row >= len(land) \
        or col >= len(land[0]) or isVisited(row, col) \
        or land[row][col] != 0:
        return False

    return True

def computeSize(row, col):
    size = 1
    visited[row][col] = 1

    for r in range(-1,2):
        for c in range(-1,2):
            if isValid(row+r, col+c) :
                size = size + computeSize(row+r,col+c)

    return size

land = [[0,2,1,0],[0,1,0,1],[1,1,0,1], [0,1,0,1]]
visited =[ [0 for i in range(4)] for j in range(4)]

computePondSizes()

Time complexity

O(n) or O(n^2) : n x n matrix