778. Swim in Rising Water 🚀

---

Solution Developed In:

The Question

For this article, we will be covering Leetcode's '778. Swim in Rising Water' question. An Advanced Graph question.

Question:

You are given an n x n integer matrix grid where each value grid[i][j] represents the elevation at that point (i, j).
The rain starts to fall. At time t, the depth of the water everywhere is t. You can swim from a square to another 4-directionally adjacent square if and only if the elevation of both squares individually are at most t. You can swim infinite distances in zero time. Of course, you must stay within the boundaries of the grid during your swim.
Return the least time until you can reach the bottom right square (n - 1, n - 1) if you start at the top left square (0, 0).

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.

Explaining The Question

This Question is rated Hard. Which is I would say is in-accurate if you're familiar with Dijkstra's Algorithm or Bellman-Ford's Algorithm or any other path finding algorithm, this question should be a Medium. If you've never encounters these algorithm, this will be impossible for the most part.

Most people will study this algorithm in Higher Education. But if you're like me, not having attending higher education mean't I hadn't the slightest clue about Path Finding Algorithms in a Graph. For me I found this question impossible to solve until I read up that it was solved by Dijkstra's Algorithm.

We're given a graph and we're asked to to traverse the entire graph and hit all nodes using the shortest path. Which sounds a lot like Kruskal's Algorithm, except we're not creating a Minimum Spanning Tree but a Shortest Path between k and all the other nodes.

How do you think Google Maps knows the shortest distance between your house and your friend's house? Shortest Path algorithms like Dijkstra's Algorithm or Bellman-Ford's Algorithm are used to find the shortest path between two locations.

Which is exactly what we're going to do. Finding the shortest path between [0][0] and the bottom right of the board in the least amount of time. Where time is represented by the depth of water, which is the value of the item on the board. Meaning, at the depth of 10, we can travel all nodes that are <= 10.

---

Recommended Knowledge

1. Graph Theory
2. Dijkstra's Algorithm
3. Path Finding Algorithms
4. Matrix
5. Matrix Traversal
6. Priority Queue
7. Heap

What do we know?

1. We're given a M x N matrix.
2. We need to start at [0][0] and end at [M][N].
3. We need to find the shortest path between [0][0] and [M][N] as defined by the depth of water.
4. The depth of water is defined by the [x][y] value of the matrix.
5. We can only traverse to adjacent nodes if the depth of water is <= the depth of the node.
6. [M][N] is unique and always unique, never duplicating.

How we're going to do it:

We're going to use Dijkstra's Algorithm to find the shortest path between [0][0] and [M][N]. The shortest path is defined as the least amount of time it takes to travel from [0][0] to [M][N]. Where time is represented by the depth of water, which is the value of the item on the board.

So we're going to re-frame the question, we're instead going to traverse all the nodes in the matrix that requires the least amount of time until we reach [M][N]. So long as they're in connection of where we currently can go, we're going to keep traversing until we reach [M][N].

1. We're going to create a Priority Queue to hold all the nodes that we need to traverse. As in Dijkstra's Algorithm, we're going to use a Priority Queue to hold the nodes that we need to traverse first. (Cheapest node first)
2. We're also going to keep note of a global time_passed variable. What this value will be, is the highest value of depth of water we visited.
3. As we know we're starting with [0][0], we're going to add it to the Priority Queue with a value of whatever is at that location (Normally 0, but don't make that assumption).
4. We will then begin performing Dijkstra's Algorithm, where we remove the 'cheapest' item from the Min-Heap and set the time_passed to the value of the item. We're also going to add the coordinates of the item to a visited Set().
5. We will also attempt to add the node above, left, right and below to the Min-Heap if they are within the bounds of the matrix and un-visited. Where we set the priority as the nodes value. Being the value of the item on the board. Thus, we've achieved the effect by only ever travelling the least amount of time.
6. We repeat this until we reach [M][N]. At this point, we know what was the highest value of depth of water we visited and so that is our answer.
7. ## Big O Notation:
8. Time Complexity: O(E * (log V)) | Right so this is a little confusing. Dijkstra's Algorithm is a O(ElogV) algorithm. Where E is the number of edges in the graph and V is the number of vertices in the graph. Which is represented by O(V^2), as in the worst case, every node and it's neighbors will be added and removed from the Min-Heap multiple times. I believe, the real time complexity of this algorithm is O( (M x N) * (Log V)). Where M is the number of rows and N is the number of columns and the Log V is the number of nodes that will be inserted and removed from the heap in logarithmic time. Thus we can reduce this to O(n (log n)).
9. Space Complexity: O(M x N) | As in the worst case, we're going to store the entire matrix within our Min-Heap or our visited set.

Is my analysis wrong? Potentially, feel free to correct me. 😁

Leetcode Results:

See Submission Link:

---

The Solution

/**
 * @param {number[][]} grid
 * @return {number}
 */
 var swimInWater = function (grid) {

    // We're going to use Dijkstra's algorithm to complete
    // to get from 0,0 to the end of the grid (Bottom Right).
    // We need to get from top left to bottom right 
    // in the shortest path. (Shortest in terms of the [i][x] value)

    // What this mean's is we will travel to the cheapest possible
    // operation relative the time passed. So at time 0, we can 
    // only travel to other 0 nodes that are in connection. Once it's 1, 
    // we can travel to other 1 nodes that are in connection. And so on and so on.

    // So instead of us manually passing time, we can use the value of the grid
    // to determine the time and the place within the queue. 

    // So, we add to a min-heap the [x,y] coordinates of the item in the grid
    // by the [x][y] value. So a grid item that is within reach and has a value
    // of 0, will be added to the top of the min-heap.


    let   time_passed = 0;                       // Max Priority of [Node] Visited
    const visit_set   = new Set();               // Don't want to visit the same node twice
    const min_heap    = new MinPriorityQueue();  // [i][x] = Priority / Time Passed

    // Min Maxes of grid and directions we can travel to.
    // Don't want to go out of bounds do we. 
    const max_rows   = grid.length - 1;
    const max_cols   = grid[0].length - 1;
    const directions = [
        [1, 0],
        [-1, 0],
        [0, 1],
        [0, -1],
    ];

    // So we firstly start off with the item in the top left corner.
    // Which could be any value. So we enqueue it as the first place to visit.
    min_heap.enqueue([0, 0], grid[0][0]); // Go to 0,0 at the cost of 0

    // While the heap is not empty and we have not reached the end of the grid.
    // Keep adding to the min-heap. 
    while (min_heap.size()) {

        // Pop node of our min heap.
        const node   = min_heap.dequeue();
        const cost   = node.priority;       // Time required to reach this node.
        const [x, y] = node.element;        // Coordinates of this node.

        // So we have not been here yet, mark it
        // We know this because, we never visit the same node twice. 
        visit_set.add(grid[x][y]);

        // So we're not at the target,
        // increment our result if we have increased.
        // As this mean's our shortest path time has increased and
        // thus so is the time passed. 
        time_passed = Math.max(cost, time_passed);

        // Are we at the target (Bottom Right of Grid)?
        // Meaning, we have found the shortest path?
        if (x === max_rows && y === max_cols) return time_passed;

        // Add the directions to the queue
        // if we have not already been there.
        //   ^
        // < x >
        //   v
        for (const direction of directions) {
            let [new_x, new_y]  = direction;
            new_x               += x; // Update x
            new_y               += y; // Update y

            // Is it out of bounds? Or we have visited it before?
            // If so, skip over this direction.
            if (new_x > max_rows || new_y > max_cols || new_x < 0 || new_y < 0 || visit_set.has(grid[new_x][new_y])) continue;

            // Enqueue the new node. Where the priority is the cost of the path.
            // Meaning, that once the time has become {x} we can visit it next. 
            min_heap.enqueue([new_x, new_y], grid[new_x][new_y]);
        }
    }    
};