Swim in Rising Water
MST & Disjoint Set DSA practice problem on Onlearn.
Difficulty: hard.
Topics: Swim in rising water problem: Algorithms to find the minimum time to reach a destination in a grid where water rises, Graph, Grid Traversal, Priority Queue, Dijkstra's Algorithm, Shortest Path, Time Complexity, Space Complexity, priority queue, dijkstra's algorithm, search space optimization, grid traversal, shortest path algorithms, binary search, bfs.
You are given an n x n integer matrix grid where grid[i][j] represents the elevation at cell (i, j). You start at (0, 0) and want to reach (n 1, n 1). You can move up, down, left, or right to an adjacent cell. The "time" to swim to a cell (i, j) is t, where t is the maximum elevation you have encountered so far along your path. You can only move from a cell (r1, c1) to an adjacent cell (r2, c2) if both grid[r1][c1] and grid[r2][c2] are less than or equal to t. Your task is to find the minimum t such that you can swim from (0, 0) to (n 1, n 1). Input Specification The input consists of an n x n integer matrix grid. Output Specification Return the minimum time t required to swim from (0, 0) to (n 1, n 1). Constraints n is the length of grid. 1 <= n <= 50 0 <= grid[i][j] < n n All values in grid are unique. Sample Test Cases Sample Input 1: Sample Output 1: Explanation: One possible path from (0,0) to (2,2) that minimizes the maximum elevation is (0,0) (1,0) (1,1) (2,1) (2,2). The elevations encountered are 0, 3, 4, 7, 8. The maximum elevation on this path is 8. There is no path with a maximum elevation less than 8.