Google Interview Question iOS Developers
Country: United States
Interview Type: Phone Interview
public int countIslands(char[][] arr)
{
int count=0;
for(int i=0;i<arr.length;i++)
{
for(int j=0;j<arr[i].length;j++)
{
if(arr[i][j]=='X')
{
count += checkForIsland(arr,i,j);
}
}
}
return count;
}
public int checkForIsland(char[][] m,int r, int c)
{
int xcount=1;
//check above
for(int k=r-1;k>=0 && k<r-4;k--)
{
if(m[k][c]=='X')
{
xcount++;
if(xcount==4)
{
return 1;
}
}else
{
break;
}
}
//check right
for(int k=c+1;k<m.length && k<c+4;k++)
{
if(m[r][k]=='X')
{
xcount++;
if(xcount==4)
{
return 1;
}
}else
{
break;
}
}
return 0;
}
//Time complexity: O(MN) Space complexity: O(1)
Here's java with O(n^2) runtime complexity (not too bad since it visits each node at most 5 times) and O(n^2) memory:
public static int countIslands(int[][] map){
if(map == null){
throw new NullPointerException();
}
if(map.length == 0){
return 0;
}
boolean[][] checked = new boolean[map.length][map[0].length];
int islandCount = 0;
for(int i = 0; i < map.length; i++){
for(int j = 0; j < map.length; j++){
if(isIsland(map, checked, i, j)){
islandCount++;
}
}
}
return islandCount;
}
private static boolean isIsland(int[][] map, boolean[][] checked, int i, int j){
//check if this is an island
boolean isIsland = map[i][j] == 1 && !checked[i][j];
//now, mark this entire island as checked
if(isIsland){
Stack<int[]> unchecked = new Stack<int[]>();
unchecked.push(new int[]{i, j});
checked[i][j] = true;
while(!unchecked.isEmpty()){
int[] position = unchecked.pop();
int iMax = i + 1 < map.length ? 1 : 0;
int iMin = i > 0 ? -1 : 0;
int jMax = j + 1 < map[0].length ? 1 : 0;
int jMin = j > 0 ? -1 : 0;
for(int iMod = i + iMin; iMod <= i + iMax; iMod++){
for(int jMod = j + jMin; jMod <= j+ jMax; jMod++){
if(iMod == i && jMod == j){
continue;
}
if(map[iMod][jMod] == 1 && !checked[iMod][jMod]){
checked[iMod][jMod] = true;
unchecked.add(new int[]{iMod, jMod});
}
}
}
}
}
return isIsland;
}
I can think of 2 approaches:
1- Brute force matrix traversal approach. O(n^2) running time.
2- Bfs graph traversal approach, where adjacent vertices of a point would be up,down,left and right. O(V+E) running time, in terms of vertices and edges.
Tell me more about how your O(V + E) is not included in O(N^2) just because you threw there letters different than N.
I never said its any better than O(n^2), I said in terms of "vertices and edges", if you've read graph theory, its O(V+E) which is not O(n). I'm being more specific.
Technically it would be equivalent to O(n^2), but if I'm describing the complexity during the interview I would like to be more specific.
public class Islands {
private static final int SEA = 0;
private static final int LAND = 1;
public int countIslands(int [][] map) {
if (map == null || map.length == 0 || map[0].length == 0) {
return 0;
}
boolean [][] visited = new boolean[map.length][map[0].length];
int counter = 0;
for (int i = 0; i < map.length; ++i) {
for (int j = 0; j < map[0].length; ++j) {
if (map[i][j] == LAND && !visited[i][j]) {
++counter;
markVisited(map, visited, i, j);
}
}
}
return counter;
}
private void markVisited(int [][] map, boolean [][] visited, int i, int j) {
if (i >= 0 && i < map.length && j >= 0 && j < map[0].length) {
if (map[i][j] == LAND && !visited[i][j]) {
visited[i][j] = true;
markVisited(map, visited, i - 1, j);
markVisited(map, visited, i, j - 1);
markVisited(map, visited, i, j + 1);
markVisited(map, visited, i + 1, j);
}
}
}
}
// O(n*m) time, O(n*m) space
How are there 4 islands? I only count 3, so I wanna make sure I'm understanding the problem right
Python:
import math
game = '1001101110100010'
game = '110001100'
#1001
#1011
#1010
#0010
def trace(f):
def g(x):
print(f.__name__, x)
value = f(x)
print('return', repr(value))
return value
return g
def setBoard(st):
numOfPoints = len(st)
n = math.sqrt(numOfPoints)
board = list()
arr = list()
count = 0
for i in st:
if(count!=n):
arr.append(i)
count+=1
if(count==n):
board.append(arr)
arr=list()
count=0
else:
board.append(arr)
arr=list()
count = 0
return board
@trace
def iterative_scheme(board):
sq = math.sqrt(len(game))
numCount = 0
for i in range(len(board)):
for j in range(int(sq)):
if(board[i][j]=='1'):
board = recursive_search(board,i,j,int(sq))
numCount += 1
return numCount
def recursive_search(board,i,j,sq):
board[i][j]='0'
if(i-1 >= 0):
if(board[i-1][j]=='1'):
return recursive_search(board,i-1,j,sq)
if(i+1<sq):
if(board[i+1][j]=='1'):
return recursive_search(board,i+1,j,sq)
if(j-1 >= 0):
if(board[i][j-1]=='1'):
return recursive_search(board,i,j-1,sq)
if(j+1 < sq):
if(board[i][j+1]=='1'):
return recursive_search(board,i,j+1,sq)
return board
board = setBoard(game)
print(iterative_scheme(board))
import math
game = '1001101110100010'
game = '110001100'
#1001
#1011
#1010
#0010
def trace(f):
def g(x):
print(f.__name__, x)
value = f(x)
print('return', repr(value))
return value
return g
def setBoard(st):
numOfPoints = len(st)
n = math.sqrt(numOfPoints)
board = list()
arr = list()
count = 0
for i in st:
if(count!=n):
arr.append(i)
count+=1
if(count==n):
board.append(arr)
arr=list()
count=0
else:
board.append(arr)
arr=list()
count = 0
return board
@trace
def iterative_scheme(board):
sq = math.sqrt(len(game))
numCount = 0
for i in range(len(board)):
for j in range(int(sq)):
if(board[i][j]=='1'):
board = recursive_search(board,i,j,int(sq))
numCount += 1
return numCount
def recursive_search(board,i,j,sq):
board[i][j]='0'
if(i-1 >= 0):
if(board[i-1][j]=='1'):
return recursive_search(board,i-1,j,sq)
if(i+1<sq):
if(board[i+1][j]=='1'):
return recursive_search(board,i+1,j,sq)
if(j-1 >= 0):
if(board[i][j-1]=='1'):
return recursive_search(board,i,j-1,sq)
if(j+1 < sq):
if(board[i][j+1]=='1'):
return recursive_search(board,i,j+1,sq)
return board
board = setBoard(game)
print(iterative_scheme(board))
import math
def setBoard(st):
numOfPoints = len(st)
n = math.sqrt(numOfPoints) #required to form N lists of N elements
board = list()
arr = list()
count = 0
for i in st:
if(count!=n):
arr.append(i)
count+=1
if(count==n):
board.append(arr)
arr = list()
count = 0
else:
board.append(arr)
arr = list()
count = 0
return board
def iterative_search(board):
sq = int(math.sqrt(len(game))) # N x N pieces, so N = sqrt(N x N)
numCount = 0
for i in range(len(board)):
for j in range(sq):
if(board[i][j]=='1'):
board = recursive_search(board,i,j,sq)
numCount += 1
return numCount
def recursive_search(board,i,j,sq):
board[i][j]='0'
if(i-1 >= 0):
if(board[i-1][j]=='1'):
return recursive_search(board,i-1,j,sq)
if(i+1<sq):
if(board[i+1][j]=='1'):
return recursive_search(board,i+1,j,sq)
if(j-1>=0):
if(board[i][j-1]=='1'):
return recursive_search(board,i,j-1,sq)
if(j+1<sq):
if(board[i][j+1]=='1'):
return recursive_search(board,i,j+1,sq)
return board
game = '1000001001101011110111111'
board = setBoard(game)
print('###INPUT###')
n=int(math.sqrt(len(game)))
splitStr=[game[i:i+n] for i in range(0, len(game), n)]
for i in splitStr:
print(i)
print('###ENDINPUT###')
print('Total Islands: {}'.format(iterative_search(board)))
import math
def setBoard(st):
numOfPoints = len(st)
n = math.sqrt(numOfPoints) #required to form N lists of N elements
board = list()
arr = list()
count = 0
for i in st:
if(count!=n):
arr.append(i)
count+=1
if(count==n):
board.append(arr)
arr = list()
count = 0
else:
board.append(arr)
arr = list()
count = 0
return board
def iterative_search(board):
sq = int(math.sqrt(len(game))) # N x N pieces, so N = sqrt(N x N)
numCount = 0
for i in range(len(board)):
for j in range(sq):
if(board[i][j]=='1'):
board = recursive_search(board,i,j,sq)
numCount += 1
return numCount
def recursive_search(board,i,j,sq):
board[i][j]='0'
if(i-1 >= 0):
if(board[i-1][j]=='1'):
return recursive_search(board,i-1,j,sq)
if(i+1<sq):
if(board[i+1][j]=='1'):
return recursive_search(board,i+1,j,sq)
if(j-1>=0):
if(board[i][j-1]=='1'):
return recursive_search(board,i,j-1,sq)
if(j+1<sq):
if(board[i][j+1]=='1'):
return recursive_search(board,i,j+1,sq)
return board
game = '1000001001101011110111111'
board = setBoard(game)
print('###INPUT###')
n=int(math.sqrt(len(game)))
splitStr=[game[i:i+n] for i in range(0, len(game), n)]
for i in splitStr:
print(i)
print('###ENDINPUT###')
print('Total Islands: {}'.format(iterative_search(board)))
void SetToInit(int * a, int i, int j, int n, int init){
int len = 1;
int k = j;
int front=j, end=j;
while (k < n){
if(a[i][k] == ‘X’)
a[i][k++] = init;
else{
end = k
break;
}
}
k = j-1
while(k >=0){
if(a[i][k] == ‘X’)
a[i][k—] = init;
else{
front = k
break;
}
}
if(i + 1 < n){
for(int m= front, m <=end; ++m)
SetToInit(a, i+1, m, n, init);
}
}
int numberOfIsland(int* a, int n)
{
int init=1;
UnionFind uf(n*n);
for(int i=0; i<n; ++i){
for(int j=0; j<n; ++j){
if (a[i][j] == ‘X’){
SetToInit(int *a, i, j, n, init);
init++;
}
}
}
return init;
}
private static int N = 35;
private static int M = 18;
private static String DATA =
"00000000000000000000000000000000000"+
"00000000000000000000000000000000000"+
"00000000000000000000000000000000000"+
"0000000000000000000X000000000000000"+
"000000000000000000XXX00000000000000"+
"000XX000000000000000000000000000000"+
"000XXXX0000000000000000000000000000"+
"0000000X000000000000000000000000000"+
"00000000000000000000000000000000000"+
"000000000000000000000X0000000000000"+
"00000000000000000000000000000000000"+
"00000000000000000000000000000000000"+
"00000000000000000000000000000000000"+
"00000000000000000000000000000000000"+
"00000000000000000000000000000000000"+
"00000000000000000000000000000000000"+
"00000000000000000000000000000000000"+
"00000000000000000000000000000000000";
public static HashSet<Integer> positions = new HashSet<Integer>();
public static void visitIsland(int index)
{
if (positions.remove(new Integer(index)))
{
int xPos = index % N;
if (xPos > 0) visitIsland(index - 1);
if (xPos < N - 1) visitIsland(index + 1);
if (index >= N) visitIsland(index - N);
if (index < N*M - N - 1) visitIsland(index + N);
}
}
public static void main(String[] args) {
for (int i = 0; i < N*M; i++)
{
if (DATA.charAt(i) == 'X')
{
positions.add(new Integer(i));
}
}
int islandCount = 0;
while (positions.size() > 0)
{
visitIsland(positions.iterator().next().intValue());
islandCount++;
}
System.out.println("Total islands: " + Integer.toString(islandCount));
}
private static int N = 35;
private static int M = 18;
private static String DATA =
"00000000000000000000000000000000000"+
"00000000000000000000000000000000000"+
"00000000000000000000000000000000000"+
"0000000000000000000X000000000000000"+
"000000000000000000XXX00000000000000"+
"000XX000000000000000000000000000000"+
"000XXXX0000000000000000000000000000"+
"0000000X000000000000000000000000000"+
"00000000000000000000000000000000000"+
"000000000000000000000X0000000000000"+
"00000000000000000000000000000000000"+
"00000000000000000000000000000000000"+
"00000000000000000000000000000000000"+
"00000000000000000000000000000000000"+
"00000000000000000000000000000000000"+
"00000000000000000000000000000000000"+
"00000000000000000000000000000000000"+
"00000000000000000000000000000000000";
public static HashSet<Integer> positions = new HashSet<Integer>();
public static void visitIsland(int index)
{
if (positions.remove(new Integer(index)))
{
int xPos = index % N;
if (xPos > 0) visitIsland(index - 1);
if (xPos < N - 1) visitIsland(index + 1);
if (index >= N) visitIsland(index - N);
if (index < N*M - N - 1) visitIsland(index + N);
}
}
public static void main(String[] args) {
// TODO code application logic here
for (int i = 0; i < N*M; i++)
{
if (DATA.charAt(i) == 'X')
{
positions.add(new Integer(i));
}
}
int islandCount = 0;
while (positions.size() > 0)
{
visitIsland(positions.iterator().next().intValue());
islandCount++;
}
System.out.println("Total islands: " + Integer.toString(islandCount));
}
private static int N = 35;
private static int M = 18;
private static String DATA =
"00000000000000000000000000000000000"+
"00000000000000000000000000000000000"+
"00000000000000000000000000000000000"+
"0000000000000000000X000000000000000"+
"000000000000000000XXX00000000000000"+
"000XX000000000000000000000000000000"+
"000XXXX0000000000000000000000000000"+
"0000000X000000000000000000000000000"+
"00000000000000000000000000000000000"+
"000000000000000000000X0000000000000"+
"00000000000000000000000000000000000"+
"00000000000000000000000000000000000"+
"00000000000000000000000000000000000"+
"00000000000000000000000000000000000"+
"00000000000000000000000000000000000"+
"00000000000000000000000000000000000"+
"00000000000000000000000000000000000"+
"00000000000000000000000000000000000";
public static HashSet<Integer> positions = new HashSet<Integer>();
public static void visitIsland(int index)
{
if (positions.remove(new Integer(index)))
{
int xPos = index % N;
if (xPos > 0) visitIsland(index - 1);
if (xPos < N - 1) visitIsland(index + 1);
if (index >= N) visitIsland(index - N);
if (index < N*M - N) visitIsland(index + N);
}
}
public static void main(String[] args) {
for (int i = 0; i < N*M; i++)
{
if (DATA.charAt(i) == 'X')
{
positions.add(new Integer(i));
}
}
int islandCount = 0;
while (positions.size() > 0)
{
visitIsland(positions.iterator().next().intValue());
islandCount++;
}
System.out.println("Total islands: " + Integer.toString(islandCount));
}
package LetsDevelopSmthing;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;
public class PositionCls {
public static int GlobalCount=0;
public static void main(String []args)
{
int x[][]={{1 ,1, 1, 0, 1, 0, 1, 1, 0, 0 },
{0, 0, 1, 1, 1, 0, 1, 0, 0, 0 },
{0 ,0, 0, 0, 0, 0, 0, 0, 0, 0 },
{0 ,0, 0, 0, 1, 0, 1, 0, 0, 0 },
{0 ,0, 0, 1, 1, 1, 1, 0, 0, 0 },
{0 ,0 ,0 ,0 ,0 ,0 ,1 ,0, 0, 1 },
{0 ,0, 0, 0, 0, 0, 0, 0, 0, 0 },
{1 ,0, 0, 0, 0, 1, 0, 0, 0, 0 },
{1 ,0, 0, 0, 0, 1, 1, 0, 0, 0 },
{1 ,0, 0, 0, 0, 0, 0, 1, 0, 1 }
};
int countNewIsland=0;boolean check;
HashMap hs=new HashMap();
for(int i=0;i<x.length;i++)
{
for(int j=0;j<x.length;j++)
{
if(x[i][j]==1){
hs.put(i+"-"+j, new Integer(0));
}
}
}
Iterator itr= hs.entrySet().iterator();
while(itr.hasNext())
{
Map.Entry me= (Entry) itr.next();
int check1=checkNeighbour((String) me.getKey(),hs);
System.out.println(" "+check1+" "+me.getKey());
if(check1>0)
GlobalCount++;
}
System.out.println(" No of island : "+GlobalCount);
}
private static int checkNeighbour(String str,HashMap h){
int count=0;
if(!h.containsKey((str))) return 0;
if(h.get(str).equals(new Integer(1))) {return 0;}
else{
h.put(str, new Integer(1));count++;
}
String[] st=str.split("-");
int x=Integer.parseInt(st[0]);
int y=Integer.parseInt(st[1]);
String up=(x-1)+"-"+y;
String down=(x+1)+"-"+y;
String left=x+"-"+(y-1);
String right=x+"-"+(y+1);
checkNeighbour(up,h);
checkNeighbour(down,h);
checkNeighbour(left,h);
checkNeighbour(right,h);
return count;
}
}
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;
public class PositionCls {
public static int GlobalCount=0;
public static void main(String []args)
{
int x[][]={{1 ,1, 1, 0, 1, 0, 1, 1, 0, 0 },
{0, 0, 1, 1, 1, 0, 1, 0, 0, 0 },
{0 ,0, 0, 0, 0, 0, 0, 0, 0, 0 },
{0 ,0, 0, 0, 1, 0, 1, 0, 0, 0 },
{0 ,0, 0, 1, 1, 1, 1, 0, 0, 0 },
{0 ,0 ,0 ,0 ,0 ,0 ,1 ,0, 0, 1 },
{0 ,0, 0, 0, 0, 0, 0, 0, 0, 0 },
{1 ,0, 0, 0, 0, 1, 0, 0, 0, 0 },
{1 ,0, 0, 0, 0, 1, 1, 0, 0, 0 },
{1 ,0, 0, 0, 0, 0, 0, 1, 0, 1 }
};
int countNewIsland=0;boolean check;
HashMap hs=new HashMap();
for(int i=0;i<x.length;i++)
{
for(int j=0;j<x.length;j++)
{
if(x[i][j]==1){
hs.put(i+"-"+j, new Integer(0));
}
}
}
Iterator itr= hs.entrySet().iterator();
while(itr.hasNext())
{
Map.Entry me= (Entry) itr.next();
int check1=checkNeighbour((String) me.getKey(),hs);
System.out.println(" "+check1+" "+me.getKey());
if(check1>0)
GlobalCount++;
}
System.out.println(" No of island : "+GlobalCount);
}
private static int checkNeighbour(String str,HashMap h){
int count=0;
if(!h.containsKey((str))) return 0;
if(h.get(str).equals(new Integer(1))) {return 0;}
else{
h.put(str, new Integer(1));count++;
}
String[] st=str.split("-");
int x=Integer.parseInt(st[0]);
int y=Integer.parseInt(st[1]);
String up=(x-1)+"-"+y;
String down=(x+1)+"-"+y;
String left=x+"-"+(y-1);
String right=x+"-"+(y+1);
checkNeighbour(up,h);
checkNeighbour(down,h);
checkNeighbour(left,h);
checkNeighbour(right,h);
return count;
}
}
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;
public class PositionCls {
public static int GlobalCount=0;
public static void main(String []args)
{
int x[][]={{1 ,1, 1, 0, 1, 0, 1, 1, 0, 0 },
{0, 0, 1, 1, 1, 0, 1, 0, 0, 0 },
{0 ,0, 0, 0, 0, 0, 0, 0, 0, 0 },
{0 ,0, 0, 0, 1, 0, 1, 0, 0, 0 },
{0 ,0, 0, 1, 1, 1, 1, 0, 0, 0 },
{0 ,0 ,0 ,0 ,0 ,0 ,1 ,0, 0, 1 },
{0 ,0, 0, 0, 0, 0, 0, 0, 0, 0 },
{1 ,0, 0, 0, 0, 1, 0, 0, 0, 0 },
{1 ,0, 0, 0, 0, 1, 1, 0, 0, 0 },
{1 ,0, 0, 0, 0, 0, 0, 1, 0, 1 }
};
int countNewIsland=0;boolean check;
HashMap hs=new HashMap();
for(int i=0;i<x.length;i++)
{
for(int j=0;j<x.length;j++)
{
if(x[i][j]==1){
hs.put(i+"-"+j, new Integer(0));
}
}
}
Iterator itr= hs.entrySet().iterator();
while(itr.hasNext())
{
Map.Entry me= (Entry) itr.next();
int check1=checkNeighbour((String) me.getKey(),hs);
System.out.println(" "+check1+" "+me.getKey());
if(check1>0)
GlobalCount++;
}
System.out.println(" No of island : "+GlobalCount);
}
private static int checkNeighbour(String str,HashMap h){
int count=0;
if(!h.containsKey((str))) return 0;
if(h.get(str).equals(new Integer(1))) {return 0;}
else{
h.put(str, new Integer(1));count++;
}
String[] st=str.split("-");
int x=Integer.parseInt(st[0]);
int y=Integer.parseInt(st[1]);
String up=(x-1)+"-"+y;
String down=(x+1)+"-"+y;
String left=x+"-"+(y-1);
String right=x+"-"+(y+1);
checkNeighbour(up,h);
checkNeighbour(down,h);
checkNeighbour(left,h);
checkNeighbour(right,h);
return count;
}
}
package LetsDevelopSmthing;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;
public class PositionCls {
public static int GlobalCount=0;
public static void main(String []args)
{
int x[][]={{1 ,1, 1, 0, 1, 0, 1, 1, 0, 0 },
{0, 0, 1, 1, 1, 0, 1, 0, 0, 0 },
{0 ,0, 0, 0, 0, 0, 0, 0, 0, 0 },
{0 ,0, 0, 0, 1, 0, 1, 0, 0, 0 },
{0 ,0, 0, 1, 1, 1, 1, 0, 0, 0 },
{0 ,0 ,0 ,0 ,0 ,0 ,1 ,0, 0, 1 },
{0 ,0, 0, 0, 0, 0, 0, 0, 0, 0 },
{1 ,0, 0, 0, 0, 1, 0, 0, 0, 0 },
{1 ,0, 0, 0, 0, 1, 1, 0, 0, 0 },
{1 ,0, 0, 0, 0, 0, 0, 1, 0, 1 }
};
int countNewIsland=0;boolean check;
HashMap hs=new HashMap();
for(int i=0;i<x.length;i++)
{
for(int j=0;j<x.length;j++)
{
if(x[i][j]==1){
hs.put(i+"-"+j, new Integer(0));
}
}
}
Iterator itr= hs.entrySet().iterator();
while(itr.hasNext())
{
Map.Entry me= (Entry) itr.next();
int check1=checkNeighbour((String) me.getKey(),hs);
System.out.println(" "+check1+" "+me.getKey());
if(check1>0)
GlobalCount++;
}
System.out.println(" No of island : "+GlobalCount);
}
private static int checkNeighbour(String str,HashMap h){
int count=0;
if(!h.containsKey((str))) return 0;
if(h.get(str).equals(new Integer(1))) {return 0;}
else{
h.put(str, new Integer(1));count++;
}
String[] st=str.split("-");
int x=Integer.parseInt(st[0]);
int y=Integer.parseInt(st[1]);
String up=(x-1)+"-"+y;
String down=(x+1)+"-"+y;
String left=x+"-"+(y-1);
String right=x+"-"+(y+1);
checkNeighbour(up,h);
checkNeighbour(down,h);
checkNeighbour(left,h);
checkNeighbour(right,h);
return count;
}
}
package LetsDevelopSmthing;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;
public class PositionCls {
public static int GlobalCount=0;
public static void main(String []args)
{
int x[][]={{1 ,1, 1, 0, 1, 0, 1, 1, 0, 0 },
{0, 0, 1, 1, 1, 0, 1, 0, 0, 0 },
{0 ,0, 0, 0, 0, 0, 0, 0, 0, 0 },
{0 ,0, 0, 0, 1, 0, 1, 0, 0, 0 },
{0 ,0, 0, 1, 1, 1, 1, 0, 0, 0 },
{0 ,0 ,0 ,0 ,0 ,0 ,1 ,0, 0, 1 },
{0 ,0, 0, 0, 0, 0, 0, 0, 0, 0 },
{1 ,0, 0, 0, 0, 1, 0, 0, 0, 0 },
{1 ,0, 0, 0, 0, 1, 1, 0, 0, 0 },
{1 ,0, 0, 0, 0, 0, 0, 1, 0, 1 }
};
int countNewIsland=0;boolean check;
HashMap hs=new HashMap();
for(int i=0;i<x.length;i++)
{
for(int j=0;j<x.length;j++)
{
if(x[i][j]==1){
hs.put(i+"-"+j, new Integer(0));
}
}
}
Iterator itr= hs.entrySet().iterator();
while(itr.hasNext())
{
Map.Entry me= (Entry) itr.next();
int check1=checkNeighbour((String) me.getKey(),hs);
System.out.println(" "+check1+" "+me.getKey());
if(check1>0)
GlobalCount++;
}
System.out.println(" No of island : "+GlobalCount);
}
private static int checkNeighbour(String str,HashMap h){
int count=0;
if(!h.containsKey((str))) return 0;
if(h.get(str).equals(new Integer(1))) {return 0;}
else{
h.put(str, new Integer(1));count++;
}
String[] st=str.split("-");
int x=Integer.parseInt(st[0]);
int y=Integer.parseInt(st[1]);
String up=(x-1)+"-"+y;
String down=(x+1)+"-"+y;
String left=x+"-"+(y-1);
String right=x+"-"+(y+1);
checkNeighbour(up,h);
checkNeighbour(down,h);
checkNeighbour(left,h);
checkNeighbour(right,h);
return count;
}
}
def run7(aa=None):
from collections import deque
ip = aa or [ [1,0,0,0,0,1,0,1,0,0],[0,0,0,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0],[0,1,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,1,1,0,0,0,0],[0,0,0,0,1,1,0,0,0,0],[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,0,1,1], ]
rx = len(ip)
ry = len(ip[0])
def _neighbor( i, j ):
nm = []
for k in [(-1,0), (0,-1), (1,0), (0,1)]:
ni = i + k[0]
nj = j + k[1]
if ( 0 <= ni < rx ) and ( 0 <= nj < ry ) and ip[ni][nj] == 1:
nm.append( ( ni, nj ) )
return nm
def _bfs( node ):
dq = deque()
dq.append( node )
while dq:
tn = dq.pop()
ip[tn[0]][tn[1]] = 0
for node in _neighbor( tn[0], tn[1] ):
if ip[node[0]][node[1]] == 1:
dq.append( node )
il = 0
for ix in xrange( rx ):
for jx in xrange( ry ):
val = ip[ix][jx]
if val == 1:
il += 1
_bfs( ( ix, jx ) )
print il
def run7(aa=None):
from collections import deque
ip = aa or [ [1,0,0,0,0,1,0,1,0,0],[0,0,0,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0],[0,1,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,1,1,0,0,0,0],[0,0,0,0,1,1,0,0,0,0],[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,0,1,1], ]
rx = len(ip)
ry = len(ip[0])
def _neighbor( i, j ):
nm = []
for k in [(-1,0), (0,-1), (1,0), (0,1)]:
ni = i + k[0]
nj = j + k[1]
if ( 0 <= ni < rx ) and ( 0 <= nj < ry ) and ip[ni][nj] == 1:
nm.append( ( ni, nj ) )
return nm
def _bfs( node ):
dq = deque()
dq.append( node )
while dq:
tn = dq.pop()
ip[tn[0]][tn[1]] = 0
for node in _neighbor( tn[0], tn[1] ):
if ip[node[0]][node[1]] == 1:
dq.append( node )
il = 0
for ix in xrange( rx ):
for jx in xrange( ry ):
val = ip[ix][jx]
if val == 1:
il += 1
_bfs( ( ix, jx ) )
print il
This is specialized for the input given. Obviously we'd need to do bounds and input checking in the real world. I took advantage of the fact that if you're scanning from left to right and from top to bottom, your bottom-leftmost X is going to have nothing below and to the right of it, and that's where you increment your islands counter.
public class Main
{
final static int N = 35;
public static void main(String[] args)
{
char[][] map = new char[][]
{{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,'X',0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,'X','X','X',0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,'X','X',0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,'X','X','X','X',0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,'X',0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,'X',0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}};
processMap(map);
}
private static void processMap(char[][] array)
{
int islandsFound = 0;
for(int i = 0; i < array.length; i++)
{
for(int j = 0; j < array[0].length; j++)
{
if(array[i][j] == 'X' &&
array[i+1][j] == 0 &&
array[i][j+1] == 0)
{
islandsFound++;
}
}
}
System.out.print("Islands Found: " + islandsFound + "\n");
}
}
public static int countIslands(char[][] map) {
int islandCount = 0;
for(int x=0; x < map.length; x++) {
for(int y=0; y < map[x].length; y++) {
if(markIslandVisited(map, x, y))
islandCount++;
}
}
return islandCount;
}
// Recursive function, marks the entire island as visited
public static boolean markIslandVisited(char[][] map, int x, int y) {
// check bounds
if(x<0 || y<0 || x>=map.length || y>=map[0].length) {
return false;
}
// capture the rest of adjacent island pieces
if(map[x][y] == UNVISITED_ISLAND) {
map[x][y] = VISITED_ISLAND;
markIslandVisited(map,x+1,y);
markIslandVisited(map,x-1,y);
markIslandVisited(map,x,y+1);
markIslandVisited(map,x,y-1);
return true;
}
return false;
}
O(n) time, O(1) space, modifies the input.
This is classic connected components problem in Graph theory. We can easily find number of islands using DFS. If the graph is connected then DFS would visit all the nodes exactly once. Now, if the graph has islands i.e. connected components then we can count number of DFS traversals needed to visit all the nodes exactly once. This is O(n*m) time complexity.
static class Coord
{
public final int X;
public final int Y;
public Coord(int x, int y)
{
this.X = x;
this.Y = y;
}
}
public static void exploreAdjLand(int[][] world, int landX, int landY, int[][] map)
{
Stack<Coord> toVisit = new Stack<>();
toVisit.push( new Coord(landX, landY));
map[landX][landY] = 1;
while( !toVisit.isEmpty() ) //Loop through adj. land discovery
{
Coord currCoords = toVisit.pop();
int x = currCoords.X;
int y = currCoords.Y;
if( x-1 >= 0 && map[x-1][y] != 1 && world[x-1][y] == 'X' ) // bounds, already discovered, and type check
{
map[x-1][y] = 1;
toVisit.push(new Coord(x-1,y));
}
if( x+1 < map.length && map[x+1][y] != 1 && world[x+1][y] == 'X' )
{
map[x+1][y] = 1;
toVisit.push(new Coord(x+1,y));
}
if( y-1 >= 0 && map[x][y-1] != 1 && world[x][y-1] == 'X' ) // bounds, already discovered, and type check
{
map[x][y-1] = 1;
toVisit.push(new Coord(x,y-1));
}
if( y+1 < map[x].length && map[x][y+1] != 1 && world[x][y+1] == 'X' )
{
map[x][y+1] = 1;
toVisit.push(new Coord(x,y+1));
}
}
}
public static int findIslands(int[][] world)
{
int[][] map = new int[world.length][world[0].length];
int islandCount = 0;
for(int x = 0; x < world.length; x++)
{
for(int y = 0; y < world[x].length; y++)
{
if(map[x][y] != 1 && world[x][y] == 'X')
{
islandCount++;
exploreAdjLand(world, x, y, map);
}
}
}
return islandCount;
}
Swift
struct Position: Hashable {
let x:Int
let y:Int
let hashValue:Int
init(x: Int,
y:Int) {
self.x = x
self.y = y
self.hashValue = "(\(x),\(y)".hashValue
}
}
func ==(lhs: Position, rhs: Position) -> Bool {
return lhs.hashValue == rhs.hashValue
}
func isPositionLand(position: Position, ocean: [[Character]]) -> Bool {
if ocean[position.y][position.x] == "x" {
return true
}
return false
}
func getNumberOfIslands(ocean: [[Character]]) -> Int {
var islands = [[Position: Character]]()
for var y = 0; y < ocean.count; y++ {
for var x = 0; x < ocean[y].count; x++ {
let position = Position(x: x, y: y)
if isPositionLand(position, ocean: ocean) {
if !isPositionAlreadyAPartOfAnIsland(position, islands: islands) {
let island = createIslandFromStartingPosition(position, ocean: ocean)
islands.append(island)
}
}
}
}
return islands.count
}
func addPositionsToIslandFromStartingPosition(startPosition: Position, inout island:[Position:Character], ocean: [[Character]]) {
let upPosition = Position(x: startPosition.x, y: startPosition.y-1)
let downPosition = Position(x: startPosition.x, y: startPosition.y+1)
let leftPosition = Position(x: startPosition.x-1, y: startPosition.y)
let rightPosition = Position(x: startPosition.x+1, y: startPosition.y)
//check up
if island[upPosition] != "x" && upPosition.y > 0 && isPositionLand(upPosition, ocean: ocean) {
island[upPosition] = "x"
addPositionsToIslandFromStartingPosition(upPosition, island: &island, ocean: ocean)
}
//check down
if island[downPosition] != "x" && downPosition.y < ocean.count && isPositionLand(downPosition, ocean: ocean) {
island[downPosition] = "x"
addPositionsToIslandFromStartingPosition(downPosition, island: &island, ocean: ocean)
}
//check left
if island[leftPosition] != "x" && leftPosition.x > 0 && isPositionLand(leftPosition, ocean: ocean) {
island[leftPosition] = "x"
addPositionsToIslandFromStartingPosition(leftPosition, island: &island, ocean: ocean)
}
//check right
if island[rightPosition] != "x" && rightPosition.x < ocean[rightPosition.y].count && isPositionLand(rightPosition, ocean: ocean) {
island[rightPosition] = "x"
addPositionsToIslandFromStartingPosition(rightPosition, island: &island, ocean: ocean)
}
}
func createIslandFromStartingPosition(position: Position, ocean: [[Character]]) -> [Position:Character] {
var island:[Position:Character] = [position:"x"]
addPositionsToIslandFromStartingPosition(position, island: &island, ocean: ocean)
return island
}
func isPositionAlreadyAPartOfAnIsland(position: Position, islands: [[Position:Character]]) -> Bool {
for island in islands {
if island[position] == "x" {
return true
}
}
return false
}
let row0:[Character] = ["o", "o", "o", "o", "o", "o", "o", "o", "o", "o"]
let row1:[Character] = ["o", "x", "o", "o", "o", "o", "o", "o", "o", "o"]
let row2:[Character] = ["o", "x", "x", "o", "o", "o", "o", "o", "x", "o"]
let row3:[Character] = ["o", "x", "o", "o", "o", "o", "o", "o", "x", "x"]
let row4:[Character] = ["o", "x", "o", "o", "x", "o", "o", "o", "x", "x"]
let row5:[Character] = ["o", "x", "o", "x", "x", "o", "o", "o", "o", "x"]
let row6:[Character] = ["o", "x", "o", "o", "x", "o", "o", "o", "o", "o"]
let row7:[Character] = ["o", "o", "o", "o", "o", "o", "o", "o", "o", "o"]
let row8:[Character] = ["o", "x", "x", "o", "o", "o", "o", "o", "o", "o"]
let row9:[Character] = ["o", "x", "o", "o", "o", "o", "o", "o", "o", "o"]
let ocean = [row0,row1,row2,row3,row4,row5,row6,row7,row8,row9]
let numberOfIslands = getNumberOfIslands(ocean)
python
wm=["00000000000000000000000000000000000",
"00000000000000000000000000000000000",
"00000000000000000000000000000000000",
"0000000000000000000X000000000000000",
"000000000000000000XXX00000000000000",
"000XX000000000000000000000000000000",
"000XXXX0000000000000000000000000000",
"0000000X000000000000000000000000000",
"00000000000000000000000000000000000",
"000000000000000000000X0000000000000",
"00000000000000000000000000000000000",
"00000000000000000000000000000000000",
"00000000000000000000000000000000000",
"00000000000000000000000000000000000",
"00000000000000000000000000000000000",
"000000000000000000000XXX00000000000",
"00000000000000X000000X0000000000000",
"00000000000000000000000000000000000"]
land=[]
def get_the_whole_island(world_map,li,lj):
global land
potential_land=[]
if li>0:
potential_land.append([world_map[li-1][lj],li-1,lj])
if lj>0:
potential_land.append([world_map[li][lj-1],li,lj-1])
if lj+1<=len(world_map[li])-1:
potential_land.append([world_map[li][lj+1],li,lj+1])
if li+1<=len(world_map)-1:
potential_land.append([world_map[li+1][lj],li+1,lj])
for i in (potential_land):
if i in land:
continue
else:
if i[0]=="X" and i not in land:
land.append(i)
get_the_whole_island(world_map,i[1],i[2])
return 0
def search(wm):
s=0
for i in range(len(wm)):
for j in range(len(wm[i])):
if wm[i][j]=="X" and [wm[i][j],i,j] not in land:
land.append([wm[i][j],i,j])
get_the_whole_island(wm,i,j)
s+=1
return s
print(search(wm))
output:
6
I found the solution in Objective C,
- (void)findIslandsInCollection {
NSArray *landArray = @[@[@"0", @"0", @"0", @"0"],
@[@"0", @"X", @"0", @"0"],
@[@"0", @"0", @"X", @"0"],
@[@"0", @"0", @"0", @"0"]
];
NSInteger islandCount = 0;
for (int i = 1; i < landArray.count-1; i++) {
// Fetch lands in current row
NSArray *landsInCurrentRow = landArray[i];
for (int j = 1; j < landsInCurrentRow.count - 1; j++) {
NSString *currentLand = landsInCurrentRow[j];
if ([currentLand isEqualToString:@"X"]) {
if ([landArray[i][j-1] isEqualToString:@"0"] &&
[landArray[i][j+1] isEqualToString:@"0"] &&
[landArray[i-1][j] isEqualToString:@"0"] &&
[landArray[i-1][j] isEqualToString:@"0"]) {
islandCount++;
}
} else {
continue;
}
}
}
NSLog(@"islandCount = %ld", (long)islandCount);;
}
//
// MiscQuestions.m
// CrackingTheCodingInterview-objc
//
// Created by David Norman on 4/24/16.
//
#import "MiscQuestions.h"
#import "Island.h"
@implementation MiscQuestions
+(void)testRun {
NSArray* mapArray = @[
@[@"X", @"X", @"O", @"O", @"O", @"O", @"O", @"X", @"X", @"X"],
@[@"X", @"X", @"O", @"O", @"O", @"O", @"O", @"X", @"X", @"X"],
@[@"O", @"O", @"O", @"O", @"O", @"O", @"O", @"O", @"X", @"X"],
@[@"O", @"O", @"O", @"O", @"O", @"O", @"O", @"O", @"O", @"O"],
@[@"O", @"O", @"O", @"O", @"X", @"X", @"O", @"O", @"X", @"O"],
@[@"O", @"O", @"O", @"O", @"X", @"X", @"O", @"O", @"X", @"O"],
@[@"O", @"O", @"O", @"O", @"O", @"O", @"O", @"O", @"O", @"O"],
@[@"O", @"O", @"O", @"O", @"O", @"O", @"O", @"O", @"O", @"O"],
@[@"O", @"O", @"O", @"O", @"O", @"O", @"O", @"O", @"O", @"O"],
@[@"X", @"X", @"O", @"O", @"O", @"O", @"O", @"O", @"O", @"O"],
@[@"X", @"X", @"O", @"O", @"O", @"O", @"O", @"O", @"O", @"O"]];
[self findIslandsInMapArrays:mapArray];
}
+(void)findIslandsInMapArrays:(NSArray*)mapArrayY {
NSMutableArray* islandArray = [NSMutableArray new];
NSIndexSet *indexArraySet = [NSIndexSet new];
NSMutableArray *outerIndexArray = [NSMutableArray new];
for ( int i = 0; i < [mapArrayY count]; i++) {
indexArraySet = [mapArrayY[i] indexesOfObjectsPassingTest:^BOOL(id _Nonnull obj, NSUInteger idx, BOOL * _Nonnull stop) {
return [obj isEqual: @"X"];
}];
NSMutableArray *indexArray = [NSMutableArray new];
[indexArraySet enumerateIndexesUsingBlock:^(NSUInteger idx, BOOL * _Nonnull stop) {
[indexArray addObject:[NSNumber numberWithInteger:idx]];
}];
if (indexArray != nil) {
[outerIndexArray addObject:indexArray];
} else {
[outerIndexArray addObject:[NSArray new]];
}
}
for (int j = 0; j < [outerIndexArray count]; j++) {
NSArray *innerIndexArray = outerIndexArray[j];
NSLog(@"innerIndexArray: %@", innerIndexArray);
for (int i = 0; i < [innerIndexArray count]; i++) {
NSNumber *xcoord = innerIndexArray[i];
if ( xcoord != nil ) {
NSPoint coordValue = NSMakePoint(xcoord.integerValue, j);
BOOL foundIsland = false;
//check new coord in all all islands
for (Island *island in islandArray) {
foundIsland = [island addPointIfWithinDistance:coordValue];
if (foundIsland) {
break;
}
}
if (!foundIsland) {
[islandArray addObject:[Island new]];
[((Island*)islandArray.lastObject).edgesArray addObject:[NSValue valueWithPoint:coordValue]];
}
}
}
}
NSLog(@"Island Array COUNT: %lu", (unsigned long)islandArray.count);
}
@end
//
// Island.m
// CrackingTheCodingInterview-objc
//
// Created by David Norman on 4/24/16.
//
#import "Island.h"
@implementation Island
- (instancetype)init
{
self = [super init];
if (self) {
self.edgesArray = [NSMutableArray new];
}
return self;
}
-(BOOL)addPointIfWithinDistance:(NSPoint)point {
BOOL result = false;
for (int i = 0; i < [self.edgesArray count]; i++) {
NSNumber *edge = self.edgesArray[i];
NSPoint islandPoint = edge.pointValue;
if (fabs(islandPoint.x - point.x) <= 1 && fabs(islandPoint.y - point.y) <= 1) {
[self.edgesArray addObject:[NSValue valueWithPoint:point]];
return true;
}
}
return result;
}
-(NSString *)description {
return self.edgesArray.description;
}
@end
Swift solution.
Use sets as hash map to collect horizontal and vertical X groups.
Recursively find and merge sets that intersect.
extension CGPoint:Hashable {
public var hashValue: Int {
return "\(x),\(y)".hashValue
}
}
var sea =
"00000000000000000000000000000000000"
+ "00000000000000000000000000000000000"
+ "00000000000000000000000000000000000"
+ "0000000000000000000X000000000000000"
+ "000000000000000000XXX00000000000000"
+ "000XX00000000000000X000000000000000"
+ "000XXXX0000000000000000000000000000"
+ "0000000X000000000000000000000000000"
+ "00000000000000000000000000000000000"
+ "000000000000000000000X0000000000000"
+ "00000000000000000000000000000000000"
+ "00000000000000000000000000000000000"
+ "00000000000000000000000000000000000"
+ "00000000000000000000000000000000000"
+ "00000000000000000000000000000000000"
+ "00000000000000000000000000000000000"
+ "00000000000000000000000000000000000"
+ "00000000000000000000000000000000000"
func numIslands(sea:String, width:Int, height:Int)->Int {
var hXs:[Set<CGPoint>] = []
var vXs:[Set<CGPoint>] = []
var xset = Set<CGPoint>()
var yset = Set<CGPoint>()
for i in 0..<sea.characters.count {
var y = i / width
var x = i % width
if x == 0 {
xset = Set<CGPoint>()
}
if Array(sea.characters)[i] == "0" {
if let _ = xset.first {
hXs.append(xset)
}
xset = Set<CGPoint>()
} else {
xset.insert(CGPointMake(CGFloat(x), CGFloat(y)))
}
y = i % height
x = (i / height)
let j = (width * y) + x
if j == 0 {
yset = Set<CGPoint>()
}
if Array(sea.characters)[j] == "0" {
if let _ = yset.first {
vXs.append(yset)
}
yset = Set<CGPoint>()
} else {
yset.insert(CGPointMake(CGFloat(x), CGFloat(y)))
}
}
if let _ = xset.first { hXs.append(xset) }
if let _ = yset.first { vXs.append(yset) }
let all = vXs + hXs
return mergeSets(all, results: []).count
}
extension Array {
var decompose:(Element, [Element])? {
return isEmpty ? nil : (self[0], Array(self[1..<count]))
}
}
func mergeSets(sets:[Set<CGPoint>], results:[Set<CGPoint>])->[Set<CGPoint>] {
if sets.count == 0 { return results + sets }
if let (head, tail) = sets.decompose {
var matches:[Set<CGPoint>] = []
var mresults = results
var t = tail
for i in 0..<tail.count {
let s = tail[i]
if head.intersect(s).count > 0 {
matches.append(head.union(s))
t.removeAtIndex(i)
break
}
}
if matches.count == 0 { mresults.append(head) }
return mergeSets(t + matches, results: mresults )
}
return []
}
let i = numIslands(sea, width: 35, height: 18)
print(i) // 4
public static int solve(int[][] matrix, boolean[][] visited, int row, int col) {
System.out.println("solve - row: " + row + " col: " + col);
if (row > 9 || col > 9) return 0;
if (visited[row][col]) return 0;
if (matrix[row][col] == 0) {
visited[row][col] = true;
return solve(matrix, visited, row+1, col) + solve(matrix, visited, row, col+1);
} else {
find(matrix, visited, row, col);
return 1;
}
}
public static void find(int[][] matrix, boolean[][] visited, int row, int col) {
System.out.println("find - row: " + row + " col: " + col);
if (row > 9 || col > 9) return;
if (row < 0 || col < 0) return;
if (visited[row][col] == true) return;
if (matrix[row][col] == 0) {
visited[row][col] = true;
return;
} else {
visited[row][col] = true;
find(matrix,visited,row+1,col);
find(matrix,visited,row-1,col);
find(matrix,visited,row,col+1);
find(matrix,visited,row,col-1);
return;
}
}
public static void main(String[] args) {
System.out.println("Solving...");
int[][] matrix = new int[][]{
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 1, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 1, 1, 1, 0, 0 },
{ 0, 1, 0, 0, 0, 0, 0, 0, 0, 1 },
{ 0, 1, 1, 0, 0, 0, 0, 1, 1, 0 },
{ 0, 0, 0, 1, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 1, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 }};
boolean[][] visited = new boolean[10][10];
System.out.println(solve(matrix, visited, 0, 0));
}
I came out whit this answer in C++:
int countIslands (int *array[], int n) { int count = 0; bool hasNeighbour; for (int i =0; i<n; i++) { for (int j=0; j<n; j++) { if (array[i][j]) { hasNeighbour = false; if (i>0) { if (array[i-1][j]) hasNeighbour = true; } if (j>0) { if (array[i][j-1]) hasNeighbour = true; } while (++j < n) { if (array[i][j]) { if (i>0) { if (array[i-1][j]) hasNeighbour = true; } } else { break; } } if (!hasNeighbour) count++; } } } return count; }Test it with
- byPaco September 15, 2015