Created
April 27, 2018 18:36
-
-
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.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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