Problem Source: 778. Swim in Rising Water
1. Understand the Problem
The problem requires a program that could return the minimum cost to goes from the top left to the bottom right cell of a grid.
The minimum cost of all paths that goes from one cell to another. With the value of the path is equals to the highest cell value.
2. First Thought
We can brute force. We can iteratively try every possible cost. With each cost, try to see if we can goes from the top left to the bottom right cells
This approach is feasible due to the small size of the grid. With just 50 rows and 50 cols per row, the grid is at most of size 2500.
Since each value in the cell can be at most square value of the rows in the grid, the maximum value of a cell can be 2500 also.
So if we want to brute force, we will have to at most goes through 2500^2 cases, which is 6250000 = 6.25 * 10^6, an acceptable runtime.
Here is the brute force solution
class Solution {
int[][] directions = {
// up
{-1, 0},
// down
{1, 0},
// left
{0, -1},
// right
{0, 1}
};
public boolean inGrid(int[][] grid, int row, int col) {
int n = grid.length;
return row >= 0 && col >= 0 && row < n && col < n;
}
class Position {
int row;
int col;
public Position(int row, int col) {
this.row = row;
this.col = col;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Position myObj = (Position) o;
return myObj.row == this.row && myObj.col == this.col;
}
@Override
public int hashCode() {
return Objects.hash(row, col);
}
}
public boolean canTraverse(int[][] grid, int cost) {
int n = grid.length;
Queue<Position> q = new LinkedList<>();
Set<Position> visited = new HashSet<>();
if (grid[0][0] > cost) {
return false;
}
// initialize where to start
Position start = new Position(0, 0);
q.add(start);
visited.add(start);
while (!q.isEmpty()) {
Position current = q.remove();
if (current.row == n - 1 && current.col == n - 1) {
return true;
}
// check for adjacent row
for (int[] dir: directions) {
int newRow = current.row + dir[0];
int newCol = current.col + dir[1];
Position adjPos = new Position(newRow, newCol);
if (inGrid(grid, newRow, newCol) && grid[newRow][newCol] <= cost && !visited.contains(adjPos)) {
q.add(adjPos);
visited.add(adjPos);
}
}
}
return false;
}
public int swimInWater(int[][] grid) {
/**
Length is 50
At most the value is 2500.
We can try for 1 to 2500 if we can go from the top to the bottom right of the maze
Each traversal will require traversing at most 50 cells
=> 125000 traversals in total
=> not too bad?
*/
int count = 0;
while (true) {
// can we go from top to bottom with that
if (canTraverse(grid, count)) {
break;
}
count ++;
}
return count;
}
}
3. Optimize
We can improve the runtime by utilizing the Prim's algorithm for establishing Minimum Spanning Tree.
View Prim's algorithm here: Prim's algorithm
Here is the code with better runtime:
public int swimInWater(int[][] grid) {
/**
What can be improve is to find the shortest path to goes from the beginnig to the end of the cells
We can applies Kruskal's algorithms:
- Start with the start,
- Check adjacents cell and add those into a heap,
- Pop the one at the top of the min heap to check. Then check the adjacents cell that is not visited of that cell
- Untill we reach the bottom right cell, stop and return.
We will have a list of visited Position, return the max value amongs those.
*/
int n = grid.length;
Set<Position> visited = new HashSet<>();
PriorityQueue<Position> pq = new PriorityQueue<>((a, b) -> a.val - b.val);
Position start = new Position(0, 0, grid[0][0]);
pq.add(start);
visited.add(start);
int result = start.val;
while (!pq.isEmpty()) {
Position current = pq.remove();
result = Math.max(result, current.val);
if (current.row == n - 1 && current.col == n - 1) {
break;
}
for (int[] dir: directions) {
int newRow = current.row + dir[0];
int newCol = current.col + dir[1];
if (inGrid(grid, newRow, newCol)) {
int newVal = grid[newRow][newCol];
Position adjPos = new Position(newRow, newCol, newVal);
if (!visited.contains(adjPos)) {
pq.add(adjPos);
visited.add(adjPos);
}
}
}
}
return result;
}
Top comments (0)