Leet Code 778. Swim in Rising Water

Example 1:

Input: grid = [[0,2],[1,3]]
Output: 3
Explanation:
At time 0, you are in grid location (0, 0).
You cannot go anywhere else because 4-directionally adjacent neighbors have a higher elevation than t = 0.
You cannot reach point (1, 1) until time 3.
When the depth of water is 3, we can swim anywhere inside the grid.

package pep.Day67;

import java.util.PriorityQueue;
import java.util.Queue;

public class LeetCode_778_Swim_in_Rising_Water {


    public int swimInWater(int[][] grid) {
        int n = grid.length, m = grid[0].length;

        Queue<Integer> pq = new PriorityQueue<>((a, b) -> {
            int r1 = a / m;
            int c1 = a % m;
            int r2 = b / m;
            int c2 = b % m;

            return grid[r1][c1] - grid[r2][c2]; // min heap
        });

        boolean[][] visited = new boolean[n][m];
        pq.add(0);
        visited[0][0] = true;

        int previousPosition = 0, time = 0, dirns[][] = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
        while (!pq.isEmpty()) {
            int rem = pq.remove();

            // jisko remove kiya uske index nikalenge
            int x = rem / m;
            int y = rem % m;

            int currentPosition = grid[x][y];
            // time unit, currentPosition - previousPosition se jo niklega
            time += currentPosition - previousPosition < 0 ? 0 : currentPosition - previousPosition;

            // agr hum pehle hi apni destination node pr aa gae, time calculate krne ke baad
            if (x == n - 1 && y == m - 1)
                return time;

            //isme agr max time wala cell visit kr liya hai toh, usse chota wala visit nhi krenge
            previousPosition = Math.max(currentPosition, previousPosition);

            for (int[] dir : dirns) {
                int row = x + dir[0];
                int col = y + dir[1];

                if (row >= 0 && col >= 0 && row < n && col < m && !visited[row][col]) {
                    visited[row][col] = true;
                    pq.add(row * m + col);
                }
            }

        }

        return time;
    }

    class Pair implements Comparable<Pair> {

        int x, y, val;

        Pair(int i, int j, int value) {
            x = i;
            y = j;
            val = value;
        }

        @Override
        public int compareTo(Pair other) {
            return this.val - other.val;
        }
    }

    public int swimInWater1(int[][] grid) {
        int row = grid.length, col = grid[0].length;

        PriorityQueue<Pair> pq = new PriorityQueue<>();
        pq.add(new Pair(0, 0, grid[0][0]));

        grid[0][0] = -1;// visited
        int ans = 0;
        int[][] dirns = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

        while (!pq.isEmpty()) {
            Pair top = pq.remove();
            int x = top.x;
            int y = top.y;
            int val = top.val;

            if (x == row - 1 && y == col - 1)
                return val;

            for (int[] dir : dirns) {
                int nx = x + dir[0];
                int ny = y + dir[1];

                if (nx < 0 || ny < 0 || nx == row || ny == col || grid[nx][ny] == -1)
                    continue;

                pq.add(new Pair(nx, ny, Math.max(val, grid[nx][ny])));
                grid[nx][ny] = -1;// visited

            }

        }

        return -1;
    }

}