Amazon Interview Question Software Engineer Interns
Country: United States
Interview Type: In-Person
class Node {
int iIndex;
int jIndex;
public Node(int iIndex, int jIndex) {
super();
this.iIndex = iIndex;
this.jIndex = jIndex;
}
public int getiIndex() {
return iIndex;
}
public void setiIndex(int iIndex) {
this.iIndex = iIndex;
}
public int getjIndex() {
return jIndex;
}
public void setjIndex(int jIndex) {
this.jIndex = jIndex;
}
public Node() {
super();
}
}
public int findNumberOfIslands(boolean[][] islands) {
boolean[][] visited= new boolean[islands.length][islands[0].length];
for(boolean row[]:visited)
Arrays.fill(row, false);
int count = 0;
for(int i=0; i < islands.length;i++) {
for(int j=0; j < islands[0].length;j++) {
if(islands[i][j] && !visited[i][j]) {
visitAdjacentPlaces(islands, visited, i, j);
count++;
}
}
}
return count;
}
public void visitAdjacentPlaces(boolean[][] islands, boolean[][] visited, int i, int j) {
Queue<Node> queue = new LinkedList<Node>();
visited[i][j] = true;
queue.add(new Node(i,j));
while(!queue.isEmpty()) {
Node node = queue.poll();
int currenti = node.getiIndex();
int currentj = node.getjIndex();
if(currenti+1 < islands.length && islands[currenti+1][currentj] && !visited[currenti+1][currentj]) {
visited[currenti+1][currentj] = true;
Node tempNode = new Node(currenti+1, currentj);
queue.add(tempNode);
}
if(currentj+1 < islands[0].length && islands[currenti][currentj+1] && !visited[currenti][currentj+1]) {
visited[currenti][currentj+1]=true;
Node tempNode = new Node(currenti, currentj+1);
queue.add(tempNode);
}
if(currentj+1 < islands[0].length && currenti+1 < islands.length && islands[currenti+1][currentj+1] && !visited[currenti+1][currentj+1]) {
visited[currenti+1][currentj+1]=true;
Node tempNode = new Node(currenti, currentj+1);
queue.add(tempNode);
}
}
}
public static void main(String[] argc) {
IsLands islandsObj = new IsLands();
boolean[][] islands = {{true,false,false,false,true,true},{false,false,true,false,true,false},{false,false,true,false,false,false}};
int count = islandsObj.findNumberOfIslands(islands);
System.out.println(count);
}
class Node {
int iIndex;
int jIndex;
public Node(int iIndex, int jIndex) {
super();
this.iIndex = iIndex;
this.jIndex = jIndex;
}
public int getiIndex() {
return iIndex;
}
public void setiIndex(int iIndex) {
this.iIndex = iIndex;
}
public int getjIndex() {
return jIndex;
}
public void setjIndex(int jIndex) {
this.jIndex = jIndex;
}
public Node() {
super();
}
}
public int findNumberOfIslands(boolean[][] islands) {
boolean[][] visited= new boolean[islands.length][islands[0].length];
for(boolean row[]:visited)
Arrays.fill(row, false);
int count = 0;
for(int i=0; i < islands.length;i++) {
for(int j=0; j < islands[0].length;j++) {
if(islands[i][j] && !visited[i][j]) {
visitAdjacentPlaces(islands, visited, i, j);
count++;
}
}
}
return count;
}
public void visitAdjacentPlaces(boolean[][] islands, boolean[][] visited, int i, int j) {
Queue<Node> queue = new LinkedList<Node>();
visited[i][j] = true;
queue.add(new Node(i,j));
while(!queue.isEmpty()) {
Node node = queue.poll();
int currenti = node.getiIndex();
int currentj = node.getjIndex();
if(currenti+1 < islands.length && islands[currenti+1][currentj] && !visited[currenti+1][currentj]) {
visited[currenti+1][currentj] = true;
Node tempNode = new Node(currenti+1, currentj);
queue.add(tempNode);
}
if(currentj+1 < islands[0].length && islands[currenti][currentj+1] && !visited[currenti][currentj+1]) {
visited[currenti][currentj+1]=true;
Node tempNode = new Node(currenti, currentj+1);
queue.add(tempNode);
}
if(currentj+1 < islands[0].length && currenti+1 < islands.length && islands[currenti+1][currentj+1] && !visited[currenti+1][currentj+1]) {
visited[currenti+1][currentj+1]=true;
Node tempNode = new Node(currenti, currentj+1);
queue.add(tempNode);
}
}
}
public static void main(String[] argc) {
IsLands islandsObj = new IsLands();
boolean[][] islands = {{true,false,false,false,true,true},{false,false,true,false,true,false},{false,false,true,false,false,false}};
int count = islandsObj.findNumberOfIslands(islands);
System.out.println(count);
}
I think the core to this problem is to be able to split it up into two functions.
The core to the problem is essentially this:
for each element in your matrix, if its land, check if its been visited already. If it has, continue, otherwise you have to explore it using whatever algorithm you want (they should all have equal performance since you have to visit all the nodes anyways).
Primary loop
def find_islands(aMatrix):
visited = []
islands = 0
for row in range(len(aMatrix)):
currow = aMatrix[row]
for col in (range(len(currow))):
if (aMatrix[row][col] == 'x' and not [row, col] in visited):
islands += 1
dfs(aMatrix, row, col, visited)
return islands
Depth First Search implementation to mark what's been visited.
def dfs(aMatrix, row, col, visited):
fringe = []
fringe.append((row, col))
while (fringe):
visiting = fringe.pop()
visited.append(visiting)
curcol = visiting[1]
currow = visiting[0]
successors = []
if (curcol + 1 < len(aMatrix)):
successors.append((currow, curcol+1))
if (currow + 1 < len(aMatrix[curcol])):
successors.append((currow+1, curcol))
if (curcol - 1 >= 0):
successors.append((currow, curcol-1))
if (currow - 1 >= 0):
successors.append((currow-1, curcol))
for successor in successors:
if successor not in visited and successor not in fringe and aMatrix[successor[0]][successor[1]] == 'x':
fringe.append(successor)
##################
# 0 1 2 3 4
#0 [[x,0,0,0,0],
#1 [0,0,x,x,0],
#2 [x,0,x,0,0],
#3 [x,0,0,0,x]]
##################
#In above case there are 4 islands -
# x then x then x,x then x
# x x
islands = [[1,0,0,0,0], [0,0,1,1,0], [1,0,1,0,0], [1,0,0,0,1]]
def findIslands():
numOfIslands = 0
for i in range(len(islands)):
for j in range(len(islands[i])):
if islands[i][j] == 1:
if i == 0 and j == 0:
numOfIslands += 1
if (islands[i-1][j] != 1) and (islands[i][j-1] != 1) and (islands[i-1][j-1] != 1):
numOfIslands += 1
print "Total number of islands = ", numOfIslands
def main():
findIslands()
if __name__ == '__main__':
main()
##################
# 0 1 2 3 4
#0 [[x,0,0,0,0],
#1 [0,0,x,x,0],
#2 [x,0,x,0,0],
#3 [x,0,0,0,x]]
##################
#In above case there are 4 islands -
# x then x then x,x then x
# x x
islands = [[1,0,0,0,0], [0,0,1,1,0], [1,0,1,0,0], [1,0,0,0,1]]
def findIslands():
numOfIslands = 0
for i in range(len(islands)):
for j in range(len(islands[i])):
if islands[i][j] == 1:
if i == 0 and j == 0:
numOfIslands += 1
if (islands[i-1][j] != 1) and (islands[i][j-1] != 1) and (islands[i-1][j-1] != 1):
numOfIslands += 1
print "Total number of islands = ", numOfIslands
def main():
findIslands()
if __name__ == '__main__':
main()
##################
# 0 1 2 3 4
#0 [[x,0,0,0,0],
#1 [0,0,x,x,0],
#2 [x,0,x,0,0],
#3 [x,0,0,0,x]]
##################
#In above case there are 4 islands -
# x then x then x,x then x
# x x
islands = [[1,0,0,0,0], [0,0,1,1,0], [1,0,1,0,0], [1,0,0,0,1]]
def findIslands():
numOfIslands = 0
for i in range(len(islands)):
for j in range(len(islands[i])):
if islands[i][j] == 1:
if i == 0 and j == 0:
numOfIslands += 1
if (islands[i-1][j] != 1) and (islands[i][j-1] != 1) and (islands[i-1][j-1] != 1):
numOfIslands += 1
print "Total number of islands = ", numOfIslands
def main():
findIslands()
if __name__ == '__main__':
main()
##################
# 0 1 2 3 4
#0 [[x,0,0,0,0],
#1 [0,0,x,x,0],
#2 [x,0,x,0,0],
#3 [x,0,0,0,x]]
##################
#In above case there are 4 islands -
# x then x then x,x then x
# x x
islands = [[1,0,0,0,0], [0,0,1,1,0], [1,0,1,0,0], [1,0,0,0,1]]
def findIslands():
numOfIslands = 0
for i in range(len(islands)):
for j in range(len(islands[i])):
if islands[i][j] == 1:
if i == 0 and j == 0:
numOfIslands += 1
if (islands[i-1][j] != 1) and (islands[i][j-1] != 1) and (islands[i-1][j-1] != 1):
numOfIslands += 1
print "Total number of islands = ", numOfIslands
def main():
findIslands()
if __name__ == '__main__':
main()
let NL[i,j] be the number of lands in the matrix A[i,j], then:
NL[i, j] = NL[i-1, j] + NL[i, j-1] - NL[i-1, j-1], if NL[i, j] is water.
NL[i, j] = NL[i-1, j] + NL[i, j-1] - NL[i-1, j-1], if NL[i, j] is land either NL[i-1,j] or NL[i, j-1] is land.
NL[i,j] = NL[i-1, j] + NL[i, j-1] - NL[i-1, j-1] - 1, if NL[i,j], NL[i-1,j] and NL[i,j-1] are land.
NL[i,j] = NL[i-1, j] + NL[i, j-1] - NL[i-1, j-1] +1, if NL[i,j] is land and NL[i-1,j] and NL[i, j-1] are not land.
The time complexity is the size of the matrix.
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace IsLandCount
{
class Program
{
static void Main(string[] args)
{
ArrayList islandCount = new ArrayList();
Console.WriteLine("Enter length and breadth of the world");
int size = int.Parse(Console.ReadLine());
Console.WriteLine("design islands");
for (int i=0; i< size;i++)
{
islandCount.Add(Console.ReadLine());
}
int count = 0;
foreach(string s in islandCount)
{
foreach(char c in s)
{
if(c == 'x' || c == 'X')
{
count++;
}
}
}
Console.WriteLine("Island Count : {0}", count);
Console.ReadLine();
}
}
}
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace IsLandCount
{
class Program
{
static void Main(string[] args)
{
ArrayList islandCount = new ArrayList();
Console.WriteLine("Enter length and breadth of the world");
int size = int.Parse(Console.ReadLine());
Console.WriteLine("design islands");
for (int i=0; i< size;i++)
{
islandCount.Add(Console.ReadLine());
}
int count = 0;
foreach(string s in islandCount)
{
foreach(char c in s)
{
if(c == 'x' || c == 'X')
{
count++;
}
}
}
Console.WriteLine("Island Count : {0}", count);
Console.ReadLine();
}
}
}
For each cell that has 1, check each adjacent cell only if it falls behind this cell or above this cell (i.e. only back check). If none of them are 1 - increment islands.
public int find(int[][] arr, int rows, int cols) {
int numOfIslands = 0;
for(int i = 0; i < rows; i++) {
for(int j = 0; j < rows; j++) {
if(
arr[i][j] == 1 &&
(j-1 < 0 || arr[i][j-1] != 1) &&
(i-1 < 0 || j-1 < 0 || arr[i-1][j-1] != 1) &&
(i-1 < 0 || arr[i-1][j]!=1) &&
(i-1 < 0 || j+1 >= cols || arr[i-1][j+1]!=1)
) {
++numOfIslands;
}
}
}
return numOfIslands;
}
Ex: Input
int arr[6][6]={
{1,1,0,0,0,1},
{0,1,0,0,0,1},
{0,0,1,1,0,0},
{0,0,0,0,0,0},
{0,0,1,1,0,0},
{0,0,0,0,1,0}
};
int find_ilands(const int arr[MAX_ROWS][MAX_COLS], const int rows, const int columns)
{
int i=0;
int j=0;
int islands = 0;
bool new_island = false;
for(i=0 ; i < rows; i++){
for(j=0; j<columns; j++){
new_island = true;
if(arr[i][j] == 1){
/*check if it is new island*/
if((i > 0) &&(j > 0)){
if((arr[i-1][j] == 1) || (arr[i][j-1] == 1) || (arr[i-1][j-1] == 1)){
new_island = false;
}
}else if(i == 0 && j > 0){
if(arr[i][j-1] == 1){
new_island = false;
}
}else if(j == 0 && i > 0){
if(arr[i-1][j] == 1){
new_island = false;
}
}
if(new_island){
islands++;
}
}
}
}
return islands;
}
int arr[6][6]={
{1,1,0,0,0,1},
{0,1,0,0,0,1},
{0,0,1,1,0,0},
{0,0,0,0,0,0},
{0,0,1,1,0,0},
{0,0,0,0,1,0}
};
int find_ilands(const int arr[][6], const int rows, const int columns)
{
int i=0;
int j=0;
int islands = 0;
bool new_island = false;
for(i=0 ; i < rows; i++){
for(j=0; j<columns; j++){
new_island = true;
if(arr[i][j] == 1){
printf("Found land at [%d] [%d]\n", i, j);
/*check if it is new island*/
if((i > 0) &&(j > 0)){
if((arr[i-1][j] == 1) || (arr[i][j-1] == 1) || (arr[i-1][j-1] == 1)){
new_island = false;
}
}else if(i == 0 && j > 0){
if(arr[i][j-1] == 1){
new_island = false;
}
}else if(j == 0 && i > 0){
if(arr[i-1][j] == 1){
new_island = false;
}
}
if(new_island){
islands++;
}
}
}
}
return islands;
}
Create a Point Class to with instance variable X and Y to store the location Matrix index .
public int findNumberOfIsland(int[][] arr){
boolean[][] visited = new boolean[arr.length][arr[0].length];
Stack<Point> stack = new Stack<>();
int noOfIsland =0;
for(int i =0 ; i < arr.length ; i++){
for(int j =0; j<arr[0].length; j++ ){
if(arr[i][j]== 1 && visited[i][j]== false){
Point p = new Point(i,j);
stack.push(p);
while(!stack.isEmpty()){
Point curr = stack.pop();
visited[curr.getX()][curr.getY()] = true;
//For checking Downward Movement
if(curr.getX()+1 < arr.length && arr[curr.getX()+1][curr.getY()] == 1 && visited[curr.getX()+1][curr.getY()] == false){
visited[curr.getX()+1][curr.getY()] = true;
Point temp = new Point(curr.getX()+1,curr.getY());
stack.push(temp);
}
//For checking Upward Movement
if(curr.getX()-1 > 0 && arr[curr.getX()-1][curr.getY()] == 1 && visited[curr.getX()-1][curr.getY()] == false ){
visited[curr.getX()-1][curr.getY()] = true;
Point temp = new Point(curr.getX()-1,curr.getY());
stack.push(temp);
}
//For checking Left Movement
if(curr.getY()-1 > 0 && arr[curr.getX()][curr.getY()-1] == 1 && visited[curr.getX()][curr.getY()-1] == false){
visited[curr.getX()][curr.getY()-1] = true;
Point temp = new Point(curr.getX(),curr.getY()-1);
stack.push(temp);
}
//For checking Right Movement
if(curr.getY()+1 < arr[0].length && arr[curr.getX()][curr.getY()+ 1] == 1 && visited[curr.getX()][curr.getY()+ 1] == false){
visited[curr.getX()][curr.getY()+ 1] = true;
Point temp = new Point(curr.getX(),curr.getY()+ 1);
stack.push(temp);
}
//For checking Upward Left Diagonal Movement
if(curr.getX()-1 > 0 && curr.getY()-1 > 0 && arr[curr.getX()-1][curr.getY()-1] == 1 && visited[curr.getX()-1][curr.getY()-1] == false){
visited[curr.getX()-1][curr.getY()-1] = true;
Point temp = new Point(curr.getX()-1,curr.getY()-1);
stack.push(temp);
}
//For checking Upward Right Diagonal Movement
if(curr.getX()-1 > 0 && curr.getY() +1 < arr[0].length && arr[curr.getX()-1][curr.getY()+1] == 1 && visited[curr.getX()-1][curr.getY()+1] == false){
visited[curr.getX()-1][curr.getY()+ 1] = true;
Point temp = new Point(curr.getX()-1,curr.getY()+ 1);
stack.push(temp);
}
//For checking Downward Left Diagonal Movement
if(curr.getX()+1 < arr.length && curr.getY()-1 > 0 && arr[curr.getX()+1][curr.getY()-1] == 1 && visited[curr.getX()+1][curr.getY()-1] == false){
visited[curr.getX()+1][curr.getY()-1] = true;
Point temp = new Point(curr.getX()-1,curr.getY()-1);
stack.push(temp);
}
//For checking Downward Right Diagonal Movement
if(curr.getX()+1 < arr.length && curr.getY() +1 < arr[0].length && arr[curr.getX()+1][curr.getY()+1] == 1 && visited[curr.getX()+1][curr.getY()+1] == false){
visited[curr.getX()+1][curr.getY()+1] = true;
Point temp = new Point(curr.getX()+1,curr.getY()+1);
stack.push(temp);
}
}
noOfIsland++;
}
}
}
return noOfIsland;
}
public int findNumberOfIsland(int[][] arr){
boolean[][] visited = new boolean[arr.length][arr[0].length];
Stack<Point> stack = new Stack<>();
int noOfIsland =0;
for(int i =0 ; i < arr.length ; i++){
for(int j =0; j<arr[0].length; j++ ){
if(arr[i][j]== 1 && visited[i][j]== false){
Point p = new Point(i,j);
stack.push(p);
while(!stack.isEmpty()){
Point curr = stack.pop();
visited[curr.getX()][curr.getY()] = true;
//For checking Downward Movement
if(curr.getX()+1 < arr.length && arr[curr.getX()+1][curr.getY()] == 1 && visited[curr.getX()+1][curr.getY()] == false){
visited[curr.getX()+1][curr.getY()] = true;
Point temp = new Point(curr.getX()+1,curr.getY());
stack.push(temp);
}
//For checking Upward Movement
if(curr.getX()-1 > 0 && arr[curr.getX()-1][curr.getY()] == 1 && visited[curr.getX()-1][curr.getY()] == false ){
visited[curr.getX()-1][curr.getY()] = true;
Point temp = new Point(curr.getX()-1,curr.getY());
stack.push(temp);
}
//For checking Left Movement
if(curr.getY()-1 > 0 && arr[curr.getX()][curr.getY()-1] == 1 && visited[curr.getX()][curr.getY()-1] == false){
visited[curr.getX()][curr.getY()-1] = true;
Point temp = new Point(curr.getX(),curr.getY()-1);
stack.push(temp);
}
//For checking Right Movement
if(curr.getY()+1 < arr[0].length && arr[curr.getX()][curr.getY()+ 1] == 1 && visited[curr.getX()][curr.getY()+ 1] == false){
visited[curr.getX()][curr.getY()+ 1] = true;
Point temp = new Point(curr.getX(),curr.getY()+ 1);
stack.push(temp);
}
//For checking Upward Left Diagonal Movement
if(curr.getX()-1 > 0 && curr.getY()-1 > 0 && arr[curr.getX()-1][curr.getY()-1] == 1 && visited[curr.getX()-1][curr.getY()-1] == false){
visited[curr.getX()-1][curr.getY()-1] = true;
Point temp = new Point(curr.getX()-1,curr.getY()-1);
stack.push(temp);
}
//For checking Upward Right Diagonal Movement
if(curr.getX()-1 > 0 && curr.getY() +1 < arr[0].length && arr[curr.getX()-1][curr.getY()+1] == 1 && visited[curr.getX()-1][curr.getY()+1] == false){
visited[curr.getX()-1][curr.getY()+ 1] = true;
Point temp = new Point(curr.getX()-1,curr.getY()+ 1);
stack.push(temp);
}
//For checking Downward Left Diagonal Movement
if(curr.getX()+1 < arr.length && curr.getY()-1 > 0 && arr[curr.getX()+1][curr.getY()-1] == 1 && visited[curr.getX()+1][curr.getY()-1] == false){
visited[curr.getX()+1][curr.getY()-1] = true;
Point temp = new Point(curr.getX()-1,curr.getY()-1);
stack.push(temp);
}
//For checking Downward Right Diagonal Movement
if(curr.getX()+1 < arr.length && curr.getY() +1 < arr[0].length && arr[curr.getX()+1][curr.getY()+1] == 1 && visited[curr.getX()+1][curr.getY()+1] == false){
visited[curr.getX()+1][curr.getY()+1] = true;
Point temp = new Point(curr.getX()+1,curr.getY()+1);
stack.push(temp);
}
}
noOfIsland++;
}
}
}
return noOfIsland;
}
// JavaScript
var matrix = [
[1, 0, 1, 0, 0],
[1, 0, 1, 1, 0],
[1, 0, 1, 0, 0],
[1, 1, 1, 0, 0],
[0, 0, 0, 0, 1]
];
var islandCount = function (matrix) {
var islands = [];
for (var row = 0; row < matrix.length; row++) {
for (var col = 0; col < matrix.length; col++) {
var nodeA = {
row: row,
col: col
};
if (matrix[row][col]) {
var indexesOfExistingIslands = [];
var existingIslandsWithNeighbors = _.filter(islands, function (island, idx) {
var islandHasNeighbors = _.some(island, function (nodeB) {
var sameCol = nodeB.col === nodeA.col;
var sameRow = nodeB.row === nodeA.row;
var rowIsOneAheadOrOneBehind = nodeB.row === (nodeA.row + 1) || nodeB.row === (nodeA.row - 1);
var colIsOneAheadOrOneBehind = nodeB.col === (nodeA.col + 1) || (nodeB.col === nodeA.col - 1);
return (sameCol && rowIsOneAheadOrOneBehind) || (sameRow && colIsOneAheadOrOneBehind);
});
if (islandHasNeighbors) {
indexesOfExistingIslands.push(idx);
}
return islandHasNeighbors;
});
if (existingIslandsWithNeighbors.length) {
if (existingIslandsWithNeighbors.length > 1) {
// create new island - a merger of all islands with neighboring nodes
var newlyMergedIsland = _.reduce(existingIslandsWithNeighbors, function (memoArr, island) {
return memoArr.concat(island);
}, []);
// filter out old islands
islands = _.filter(islands, function (island, idx) {
return !_.contains(indexesOfExistingIslands, idx);
});
islands.push(newlyMergedIsland)
} else {
// push node into single island with neighboring nodes
existingIslandsWithNeighbors[0].push(nodeA);
}
} else {
// no islands with neighboring nodes - create new island
var newIsland = [nodeA];
islands.push(newIsland);
}
}
}
}
return islands.length;
};
// JavaScript
var matrix = [
[1, 0, 1, 0, 0],
[1, 0, 1, 1, 0],
[1, 0, 1, 0, 0],
[1, 1, 1, 0, 0],
[0, 0, 0, 0, 1]
];
var islandCount = function (matrix) {
var islands = [];
for (var row = 0; row < matrix.length; row++) {
for (var col = 0; col < matrix.length; col++) {
var nodeA = {
row: row,
col: col
};
if (matrix[row][col]) {
var indexesOfExistingIslands = [];
var existingIslandsWithNeighbors = _.filter(islands, function (island, idx) {
var islandHasNeighbors = _.some(island, function (nodeB) {
var sameCol = nodeB.col === nodeA.col;
var sameRow = nodeB.row === nodeA.row;
var rowIsOneAheadOrOneBehind = nodeB.row === (nodeA.row + 1) || nodeB.row === (nodeA.row - 1);
var colIsOneAheadOrOneBehind = nodeB.col === (nodeA.col + 1) || (nodeB.col === nodeA.col - 1);
return (sameCol && rowIsOneAheadOrOneBehind) || (sameRow && colIsOneAheadOrOneBehind);
});
if (islandHasNeighbors) {
indexesOfExistingIslands.push(idx);
}
return islandHasNeighbors;
});
if (existingIslandsWithNeighbors.length) {
if (existingIslandsWithNeighbors.length > 1) {
// create new island - a merger of all islands with neighboring nodes
var newlyMergedIsland = _.reduce(existingIslandsWithNeighbors, function (memoArr, island) {
return memoArr.concat(island);
}, []);
// filter out old islands
islands = _.filter(islands, function (island, idx) {
return !_.contains(indexesOfExistingIslands, idx);
});
islands.push(newlyMergedIsland)
} else {
// push node into single island with neighboring nodes
existingIslandsWithNeighbors[0].push(nodeA);
}
} else {
// no islands with neighboring nodes - create new island
var newIsland = [nodeA];
islands.push(newIsland);
}
}
}
}
return islands.length;
};
// JavaScript
var matrix = [
[1, 0, 1, 0, 0],
[1, 0, 1, 1, 0],
[1, 0, 1, 0, 0],
[1, 1, 1, 0, 0],
[0, 0, 0, 0, 1]
];
var islandCount = function (matrix) {
var islands = [];
for (var row = 0; row < matrix.length; row++) {
for (var col = 0; col < matrix.length; col++) {
var nodeA = {
row: row,
col: col
};
if (matrix[row][col]) {
var indexesOfExistingIslands = [];
var existingIslandsWithNeighbors = _.filter(islands, function (island, idx) {
var islandHasNeighbors = _.some(island, function (nodeB) {
var sameCol = nodeB.col === nodeA.col;
var sameRow = nodeB.row === nodeA.row;
var rowIsOneAheadOrOneBehind = nodeB.row === (nodeA.row + 1) || nodeB.row === (nodeA.row - 1);
var colIsOneAheadOrOneBehind = nodeB.col === (nodeA.col + 1) || (nodeB.col === nodeA.col - 1);
return (sameCol && rowIsOneAheadOrOneBehind) || (sameRow && colIsOneAheadOrOneBehind);
});
if (islandHasNeighbors) {
indexesOfExistingIslands.push(idx);
}
return islandHasNeighbors;
});
if (existingIslandsWithNeighbors.length) {
if (existingIslandsWithNeighbors.length > 1) {
// create new island - a merger of all islands with neighboring nodes
var newlyMergedIsland = _.reduce(existingIslandsWithNeighbors, function (memoArr, island) {
return memoArr.concat(island);
}, []);
// filter out old islands
islands = _.filter(islands, function (island, idx) {
return !_.contains(indexesOfExistingIslands, idx);
});
islands.push(newlyMergedIsland)
} else {
// push node into single island with neighboring nodes
existingIslandsWithNeighbors[0].push(nodeA);
}
} else {
// no islands with neighboring nodes - create new island
var newIsland = [nodeA];
islands.push(newIsland);
}
}
}
}
return islands.length;
};
Connected Components algorithm in a graph
public class Solution {
public static class Point {
int row;
int col;
public Point(int row, int col) {
this.row = row;
this.col = col;
}
public boolean isValid(char[][] grid) {
int rows = grid.length;
int columns = grid[0].length;
return row >= 0 && row < rows && col >= 0 && col < columns && grid[row][col] == '1';
}
}
public static Point[] directions = {new Point(1,0),new Point(-1,0),new Point(0,1),new Point(0,-1)};
public int numIslands(char[][] grid) {
int rows = grid.length;
if(rows == 0){
return 0;
}
int columns = grid[0].length;
int component = 0;
boolean[][] visited = new boolean[rows][columns];
for (int i = 0; i< rows; i++) {
for (int j = 0; j< columns; j++) {
if (grid[i][j] == '1' && !visited[i][j]) {
visited[i][j] = true;
dfs(new Point(i,j), grid, visited);
component ++;
}
}
}
return component;
}
void dfs(Point start, char[][] grid, boolean[][] visited){
int rows = grid.length;
int columns = grid[0].length;
for(Point dir : directions) {
Point newPoint = new Point(start.row + dir.row, start.col + dir.col);
if(newPoint.isValid(grid) && !visited[newPoint.row][newPoint.col]) {
visited[newPoint.row][newPoint.col] = true;
dfs(newPoint, grid, visited);
}
}
}
}
this is the way I approach
typedef struct _co_ordinates{
int x;
int y;
} co_ordinates;
bool isValid(co_ordinates c, int size){
return (c.x >= 0 && c.x < size && c.y >= 0 && c.y < size) ? true : false;
}
co_ordinates left(co_ordinates c){
return { c.x - 1, c.y };
}
co_ordinates right(co_ordinates c){
return{ c.x + 1, c.y };
}
co_ordinates up(co_ordinates c){
return{ c.x, c.y - 1};
}
co_ordinates down(co_ordinates c){
return{ c.x, c.y + 1};
}
co_ordinates(*direction[4])(co_ordinates) = { up, right, down, left };
int countIsland(int** arr, int size){
int sum = 0;
for (int i = 0; i < size; i++){
for (int j = 0; j < size; j++){
if (arr[i][j] > 1) continue;
if (arr[i][j] == 0){
arr[i][j] = 2;
continue;
}
if (arr[i][j] == 1){
arr[i][j] = 3;
sum += countIslandUntil(arr, i, j, size);
}
}
}
return sum;
}
int countIslandUntil(int **arr, int x, int y, int size){
queue<co_ordinates> q;
co_ordinates c = { x, y };
q.push(c);
while (!q.empty()){
co_ordinates c = q.front();
q.pop();
int i = 4;
while (i){
co_ordinates temp = direction[--i](c);
if (isValid(temp,size) && arr[temp.x][temp.y] == 1){
arr[temp.x][temp.y] = 3;
q.push(temp);
}
}
}
return 1;
}
Simple dfs sol
public static int noOfIslands(int[][] matrix){
int count = 0;
int rows = matrix.length;
int cols = matrix[0].length;
for(int i = 0; i < rows; i++){
for(int j = 0; j < cols; j++){
if(matrix[i][j] == 1){
++count;
setZero(matrix, i, j, rows, cols);
}
}
}
return count;
}
public static void setZero(int[][] m, int i, int j, int rows, int cols){
if(i < 0 || j < 0 || i >= rows || j >= cols)
return;
if(m[i][j] == 0)
return;
m[i][j] = 0;
setZero(m, i-1, j, rows, cols);
setZero(m, i+1, j, rows, cols);
setZero(m, i, j-1, rows, cols);
setZero(m, i, j+1, rows, cols);
}
Assumptions : land and water space is represented as a matrix with m rows and n columns.
matrix[i][j] = 'x' represents land and matrix [i][j] = ' ' (space) represents water.
//visited matrix keeps track of which vertices are visited bool ** visited; // count number of islands int numIslands = 0; // function to mark connected islands parts as visited. void exploreConnected( int i, int j); int main (int argc, char ** argv){ int m = 100; // or take input from user int n = 200; // or take input from user // initialize first level of visited matrix - no need of calloc here. visited = (bool **) malloc( m, sizeof(bool *) ); if( visited == NULL ) return -1; // initialize second level of visited matrix - should be zeroed for( int i = 0; i < m; i++ ){ visited[i] = (bool *) calloc( n, sizeof(bool) ); if(visited[i] == NULL) return -1; } // traverse nodes in row major fashion for( int i = 0; i < m; i++){ for(int j = 0; j < n; j++){ // do not process a node if it is not island or processed already if( matrix[i][j] == ' ' || visited[i][j] == true) continue; // we have found a new land! numIslands++; // now explore new land. exploreConnected( i, j ); } } printf( "Num of islands = %d\n", numIslands ); } void exploreConnected( int i, int j ){ visited[i][j] = true; // check and explore right node in the same row. if( j < n-1 && matrix[i][j+1] == 'x' && visited[i][j+1] == false) exploreConnected( i, j+1 ); // check and explore lower left node if( i < m-1 && j > 0 && matrix[i+1][j-1] == 'x' && visited[i+1][j-1] == false ) exploreConnected( i+1, j-1 ); // check and explore lower node if( i < m-1 && matrix[i+1][j] =='x' && visited[i+1][j] == false) exploreConnected( i+1, j ); // check and explore lower right node if( i < m-1 && j < n-1 && matrix[i+1][j+1] == 'x' && visited[i+1][j+1] == false) exploreConnected( i+1, j+1 ); }As the for loop in the main function goes in row major order, we only need to check four adjacent nodes instead of all 8.
- nviladkar February 20, 2016Time complexity : O(m*n)
Space complexity : O(m*n)