The interview happened online over Amazon Chime.
The problem statement: Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.
It was a variation of the following leetcode question.
https://leetcode.com/problems/number-of-islands/
In the above question of leetcode, the island is defined as An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically.
In the question asked in Amazon interview, the island was defined as An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically and diagonally.
Hence the solution should consider checking 8 surroinding values (TL, T, TR, R, BR, B, BL, L) in the matrix rather then 4 surrouding values (T, R, B, L).
Following was the solution proposed.
public class Solution {
public int NumIslands(char[][] grid) {
var m = grid.Length;
var n = grid[0].Length;
var map = new bool[m][];
var count = 0;
for(var i = 0;i<m;i++)
{
map[i] = new bool[n];
}
for(var i = 0;i<m;i++)
{
for(var j = 0;j<n;j++)
{
if(grid[i][j] == '1' && !map[i][j])
{
CheckForValidity(grid, m, n, i, j, map);
count++;
}
}
}
return count;
}
public void CheckForValidity(char[][] grid, int m, int n, int i, int j, bool[][] map)
{
Console.WriteLine(i + ":" + j);
if(i<0 || j < 0 || i >= m || j >= n || grid[i][j] != '1' || map[i][j])
{
return;
}
map[i][j] = true;
var row = new int[] {-1, -1, -1, 0, 0, 1, 1, 1};
var col = new int[] { -1, 0, 1, -1, 1, -1, 0, 1};
for(var k = 0;k<8;k++)
{
CheckForValidity(grid,m , n, i+row[k], j + col[k], map);
}
}
}