Amazon Interview Question
Backend DevelopersCountry: United States
For this problem, I am assuming we can modify the original matrix. In that case, scan through the islands matrix, and if we find an island that is surrounded by islands, remove it by setting it to 0. I present my solution in Python below. TC:- O(n*m) where n and m represents the number of rows and cols. SC:- O(1) since we are modifying the matrix in-place.
My solution:
def removeIslands(islandsMatrix):
rows, cols = len(islandsMatrix), len(islandsMatrix[0])
def isCoordinateWater(i, j):
return 0 <= i < rows and 0 <= j < cols and islandsMatrix[i][j] == '0'
for i, row in enumerate(islandsMatrix):
for j, sq in enumerate(row):
if sq == '1':
coordinates = [(i+1,j), (i-1,j), (i,j+1), (i,j-1)]
if all([isCoordinateWater(x, y) for x, y in coordinates]):
islandsMatrix[i][j] = '0'
return islandsMatrix
Test Code:
islands = [
['1', '1', '1', '1', '1', '1'],
['1', '0', '0', '0', '0', '1'],
['1', '0', '0', '1', '0', '1'],
['1', '0', '0', '0', '0', '1'],
['1', '1', '1', '1', '1', '1']
]
from pprint import pprint
pprint(removeIslands(islands))
'''
Output:
[
['1', '1', '1', '1', '1', '1'],
['1', '0', '0', '0', '0', '1'],
['1', '0', '0', '0', '0', '1'],
['1', '0', '0', '0', '0', '1'],
['1', '1', '1', '1', '1', '1']
]
'''
@prudent_programmer
What about this input ?
islands = [
['1', '1', '1', '1', '1','1' ,'1'],
['1', '0', '0', '0', '0', '0','1'],
['1', '0', '0', '1','1', '0', '1'],
['1', '0', '0', '0', '0', '1','1'],
['1', '1', '1', '1', '1', '1','1']
]
your code would generate this output:
islands = [
['1', '1', '1', '1', '1','1' ,'1'],
['1', '0', '0', '0', '0', '0','1'],
['1', '0', '0', '1','1', '0', '1'],
['1', '0', '0', '0', '0', '1','1'],
['1', '1', '1', '1', '1', '1','1']
]
but the correct output is:
islands = [
['1', '1', '1', '1', '1','1' ,'1'],
['1', '0', '0', '0', '0', '0','1'],
['1', '0', '0', '0','0', '0', '1'],
['1', '0', '0', '0', '0', '1','1'],
['1', '1', '1', '1', '1', '1','1']
]
@sbdul Thank you so much.Nice catch. I didn't consider the edge cases and consider if the islands are stringed together or if they lie near the boundaries. I fixed my code and use DFS for searching through the grid and remove the islands as necessary. I have attached the rewritten code in Python below.
Solution:
def removeIslands(islandsMatrix):
rows, cols = len(islandsMatrix), len(islandsMatrix[0])
def dfs(i, j):
# Check if the coordinate is a boundary
if i in [0, rows-1] or j in [0, cols-1]:
return True
# Check if the coordinate is invalid
if i < 0 or i >= rows \
or j < 0 or j >= cols \
or islandsMatrix[i][j] != '1':
return False
islandsMatrix[i][j] = '#' # Use '#' for marking
coordinates = [(i+1,j), (i-1,j), (i,j+1), (i,j-1)]
# If you find that all four sides are surrounded by water
# then remove the islands by setting it to 0
if not any(dfs(x, y) for x,y in coordinates):
islandsMatrix[i][j] = '0'
else: # Else, set it to 1
islandsMatrix[i][j] = '1'
for i, row in enumerate(islandsMatrix):
for j, sq in enumerate(row):
dfs(i, j)
return islandsMatrix
Test code:
from pprint import pprint
islands1 = [
['1', '1', '1', '1', '1', '1', '1'],
['1', '0', '0', '0', '0', '0', '1'],
['1', '0', '0', '1', '1', '0', '1'],
['1', '0', '0', '0', '0', '1', '1'],
['1', '1', '1', '1', '1', '1', '1']
]
pprint(removeIslands(islands1))
print('--'* 20)
island2 = [
['1', '1', '1', '1', '1', '1', '1'],
['1', '0', '0', '0', '0', '0', '1'],
['1', '0', '1', '1', '0', '1', '1'],
['1', '0', '1', '0', '0', '0', '1'],
['1', '1', '0', '0', '0', '1', '1'],
['1', '1', '1', '1', '1', '1', '1']
]
pprint(removeIslands(island2))
Output:
[['1', '1', '1', '1', '1', '1', '1'],
['1', '0', '0', '0', '0', '0', '1'],
['1', '0', '0', '0', '0', '0', '1'],
['1', '0', '0', '0', '0', '1', '1'],
['1', '1', '1', '1', '1', '1', '1']]
----------------------------------------
[['1', '1', '1', '1', '1', '1', '1'],
['1', '0', '0', '0', '0', '0', '1'],
['1', '0', '0', '0', '0', '1', '1'],
['1', '0', '0', '0', '0', '0', '1'],
['1', '1', '0', '0', '0', '1', '1'],
['1', '1', '1', '1', '1', '1', '1']]
@prudent_programmer
Nice solution, another neat solution is to use union find data structure.
Start by connecting all boundary cells to a dummy node and then to iterate through the grid and for all the '1' cells check if one of their neighbors is connected to the dummy node, and if so, connect the current cell to the dummy node as well, and at the end iterate through the grid and set all '1' cells that aren't connected to the dummy node to '0'.
static void RemoveComponents(int[,] board)
{
for (int c = 1; c < board.GetLength(1) - 1; c++){
if (board[1, c] == 1)
Traverse(board, 1, c);
if (board[board.GetLength(0) - 2, c] == 1)
Traverse(board, board.GetLength(0) - 2, c);
}
for (int r = 2; r < board.GetLength(0) - 2; r++){
if (board[r, 1] == 1)
Traverse(board, r, 1);
if (board[r, board.GetLength(1) - 2] == 1)
Traverse(board, r, board.GetLength(1) - 2);
}
for(int r = 1; r < board.GetLength(0) - 1; r++)
for (int c = 1; c < board.GetLength(1) - 1; c++)
if (board[r, c] == -1)
board[r, c] = 1;
else if (board[r, c] == 1)
board[r, c] = 0;
}
static void Traverse(int[,] board, int row, int col)
{
board[row, col] = -1;
for (int r = row - 1; r <= row + 1; r++)
for(int c = col - 1; c <= col + 1; c++){
if ((r == row && c == col) || r < 1 || r >= board.GetLength(0) - 1 ||
c < 1 || c >= board.GetLength(1) - 1)
continue;
if(board[r, c] == 1)
Traverse(board, r, c);
}
}
length = int(input())
- Gaurav1wani March 15, 2018flag = 0
arr = [[int(j) for j in input()] for i in range(length)]
print("Array begins here: \n")
for row in arr:
print(' '.join([str(elem) for elem in row]))
#Check for all elements on boundry are 1
for i in range(length):
if arr[0][i] != 1:
flag = 1
print("Issue in first row")
for i in range(length):
if arr[length-1][i] != 1:
flag = 1
print("Issue in last row")
for i in range(length):
if arr[i][0] != 1:
flag = 1
print("Issue in first Column")
for i in range(length):
if arr[i][length-1] != 1:
flag = 1
print("Issue in last column")
#Iterate inside and make it Zero
if flag != 1:
for i in range(1,length-1):
for j in range(1,length-1):
arr[i][j] = 0
print("Final Values in array are: \n")
for row in arr:
print(' '.join([str(elem) for elem in row]))