三刷 07/2022
Version #3 Union Find
Time O(MN) - we have 4 MN union operations, union with size rank and path compression will result in amortized O(1) time
Space O(MN)
Runtime: 6 ms, faster than 25.46% of Java online submissions for Max Area of Island.
Memory Usage: 48 MB, less than 21.47% of Java online submissions for Max Area of Island.
class Solution {
private static int ISLAND = 1;
class UnionFind {
private int[] size;
private int[] id;
private int rows;
private int cols;
int maxSize = 0;
public UnionFind(int[][] grid) {
rows = grid.length;
cols = grid[0].length;
size = new int[rows * cols];
id = new int[rows * cols];
for (int y = 0; y < rows; y++) {
for (int x = 0; x < cols; x++) {
int index = getIndex(cols, y, x);
if (grid[y][x] == 1) {
maxSize = 1;
size[index] = 1;
id[index] = index;
}
}
}
}
public int root(int i) {
while (id[i] != i) {
id[i] = id[id[i]];
i = id[i];
}
return i;
}
public void union(int p, int q) {
int rootP = root(p);
int rootQ = root(q);
if (rootP == rootQ) {
return;
}
if (size[rootP] < size[rootQ]) {
id[rootP] = rootQ;
size[rootQ] += size[rootP];
maxSize = Math.max(maxSize, size[rootQ]);
} else {
id[rootQ] = rootP;
size[rootP] += size[rootQ];
maxSize = Math.max(maxSize, size[rootP]);
}
}
public int getMaxSize() {
return maxSize;
}
}
public int getIndex(int cols, int y, int x) {
return y * cols + x;
}
private int[] dx = new int[]{1, 0, -1, 0};
private int[] dy = new int[]{0, -1, 0, 1};
public int maxAreaOfIsland(int[][] grid) {
int rows = grid.length;
int cols = grid[0].length;
UnionFind uf = new UnionFind(grid);
for (int y = 0; y < rows; y++) {
for (int x = 0; x < cols; x++) {
if (grid[y][x] != ISLAND) {
continue;
}
int index = getIndex(cols, y, x);
for (int i = 0; i < 4; i++) {
int ny = y + dy[i];
int nx = x + dx[i];
if (ny < 0 || nx < 0 || ny >= rows || nx >= cols || grid[ny][nx] != ISLAND) {
continue;
}
uf.union(index, getIndex(cols, ny, nx));
}
}
}
return uf.getMaxSize();
}
}
二刷 06/2022
We could also use stack based DFS to avoid using recursion
Version #2 DFS without changing the original matrix
Time O(MN)
Space O(MN)
Runtime: 4 ms, faster than 52.28% of Java online submissions for Max Area of Island.
Memory Usage: 47.4 MB, less than 48.23% of Java online submissions for Max Area of Island.
class Solution {
public int maxAreaOfIsland(int[][] grid) {
int rows = grid.length;
int cols = grid[0].length;
boolean[][] visited = new boolean[rows][cols];
int max = 0;
for (int y = 0; y < rows; y++) {
for (int x = 0; x < cols; x++) {
if (grid[y][x] == 1 && !visited[y][x]) {
visited[y][x] = true;
max = Math.max(max, dfs(grid, visited, y, x));
}
}
}
return max;
}
private static int[] dx = new int[]{1, 0, -1, 0};
private static int[] dy = new int[]{0, -1, 0, 1};
// Return how many 1s are in current island
private int dfs(int[][] grid, boolean[][] visited, int y, int x) {
int count = 1;
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx < 0 || ny < 0 || nx >= grid[0].length || ny >= grid.length || visited[ny][nx] || grid[ny][nx] != 1) {
continue;
}
visited[ny][nx] = true;
count += dfs(grid, visited, ny, nx);
}
return count;
}
}
Version #1 DFS
43.59 %
class Solution {
public int maxAreaOfIsland(int[][] grid) {
// iterate through the grid, if we see any 1, we try to expand this island
// set any visited grid to 0
int max = 0;
for (int y = 0; y < grid.length; y++) {
for (int x = 0; x < grid[0].length; x++) {
if (grid[y][x] == 1) {
max = Math.max(max, dfs(grid, x, y));
}
}
}
return max;
}
private int[] dx = new int[]{1, 0, -1, 0};
private int[] dy = new int[]{0, -1, 0, 1};
private int dfs(int[][] grid, int x, int y) {
// return the size of current island
int size = 1;
grid[y][x] = 0;
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 0 && nx < grid[0].length && ny >= 0 && ny < grid.length
&& grid[ny][nx] == 1) {
size += dfs(grid, nx, ny);
}
}
return size;
}
}
No comments:
Post a Comment