DEV Community

truongductri01
truongductri01

Posted on

778. Swim in Rising Water

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;
    }
}
Enter fullscreen mode Exit fullscreen mode

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;

    }
Enter fullscreen mode Exit fullscreen mode

Top comments (0)