Skip to content

Instantly share code, notes, and snippets.

@ashish0x90
Created April 27, 2018 18:36
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save ashish0x90/6a0cedfa28ed3834911f9ac6bab1e50b to your computer and use it in GitHub Desktop.
Save ashish0x90/6a0cedfa28ed3834911f9ac6bab1e50b to your computer and use it in GitHub Desktop.
Island finder, contains iterative as well as recursive method with sanity test input.
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Deque;
import java.util.List;
public final class IslandFinder {
// Entry point
public List<Island> findIslands(boolean[][] map) {
if (map.length == 0) {
return Collections.emptyList();
}
boolean[][] visited = new boolean[map.length][map[0].length];
List<Island> islands = new ArrayList<>();
for (int i = 0; i < map.length; i++) {
for (int j = 0; j < map[0].length; j++) {
if (map[i][j] && !visited[i][j]) {
Island island = new Island();
findIslandRecursive(new Point(i, j), map, visited, island);
//findIslandIterative(new Point(i, j), map, visited, island); // would use interface-implementation(s),
// but skipping it for now.
islands.add(island);
}
}
}
return islands;
}
// code v0 during 3rd interview round, recursive approach. Space complexity - O(n), Time complexity O(n),
// n = number of points in map
private void findIslandRecursive(Point origin, boolean[][] map, boolean[][] visited, Island island) {
for (Point neighbour : getNeighbours(origin, map)) {
int rowIndex = neighbour.getRowIndex();
int columnIndex = neighbour.getColumnIndex();
if (map[rowIndex][columnIndex] && !visited[rowIndex][columnIndex]) {
island.addPoint(neighbour);
visited[rowIndex][columnIndex] = true;
findIslandRecursive(neighbour, map, visited, island);
}
}
}
// code v1 during 4th interview round, iterative memory optimized approach, Space complexity - O(n), Time complexity O(n),
// n = number of points in map
private void findIslandIterative(Point origin, boolean[][] map, boolean[][] visited, Island island) {
Deque<Point> expansionTracker = new ArrayDeque<>();
expansionTracker.addFirst(origin);
while (!expansionTracker.isEmpty()) {
Point neighbour = expansionTracker.removeFirst();
int rowIndex = neighbour.getRowIndex();
int columnIndex = neighbour.getColumnIndex();
if (map[rowIndex][columnIndex] && !visited[rowIndex][columnIndex]) {
island.addPoint(neighbour);
}
visited[rowIndex][columnIndex] = true;
for (Point each: getNeighbours(neighbour, map)) {
if (map[each.getRowIndex()][each.getColumnIndex()] && !visited[each.getRowIndex()][each.getColumnIndex()]) {
expansionTracker.addFirst(each);
}
}
}
}
// Expansion util method
private List<Point> getNeighbours(Point origin, boolean[][] map) {
List<Point> points = new ArrayList<>();
for (int r = -1; r <= 1; r++) { // generate all [i-1..+1, j-1..+1] points
for (int c = -1; c <= 1; c++) {
int rowIndex = r + origin.getRowIndex();
int columnIndex = c + origin.getColumnIndex();
if (rowIndex >= map.length || rowIndex < 0 || columnIndex >= map[0].length || columnIndex < 0) { // map bound checks.
continue;
}
points.add(new Point(rowIndex, columnIndex));
}
}
return points;
}
public static final class Point {
private int rowIndex;
private int columnIndex;
public Point(int rowIndex, int columnIndex) {
this.rowIndex = rowIndex;
this.columnIndex = columnIndex;
}
public int getRowIndex() {
return rowIndex;
}
public int getColumnIndex() {
return columnIndex;
}
}
public static final class Island {
private List<Point> points;
public Island() {
this.points = new ArrayList<>();
}
public void addPoint(Point point) {
this.points.add(point);
}
public Iterable<Point> getPoints() {
return points;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment