You are given an n x n grid of integers
Each cell in the grid represents the elevation of the land at that cell
The objective is to determine the minimum time T such that you can swim from the top-left cell (0,0) to the bottom right cell (n-1, n-1), assuming:
1. At time T, you can swim in any cell whose elevation <= T
2. You can move up, down, left or right from one cell to another
🔭Key Observations
1. Elevation as a Constraint:
- you can only move into a cell if T >= elevation[cell]
- at time T, all cells with elevation <= T are "accessible"
2. Goal:
- minimize T, so you reach (n-1, n-1) with the smallest possible elevation threshold
3. Pathfinding:
- you are essentially trying to find a path from (0,0) to (n-1, n-1) where the maximum elevation you encounter on the path is minimized
💡 Approach 1 : Dijkstra’s Algorithm
treat the problem as a graph traversal problem, where each cell is a node, and the elevation acts as the "cost" to enter the cell
- use a priority queue (min-heap) to explore the grid
- at each step, process the cell with the lowest elevation first
- track the maximum elevation encountered so far to reach each cell
⌛ Complexity Analysis
Time Complexity:
O(n^2 log n), since each of the n^2 cells is processed and pushed into the priority queue
^ this is an improvement over the brute force approach which warrants an exponential time complexity O(2^n)
Space Compleixty:
O(n^2) for the auxilary space of the priority queue and the visited array
💻 Implementation of Solution
class Solution {private: const vector<pair<int, int>> directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};public: int swimInWater(vector<vector<int>>& grid) { int n = grid.size(); // priority queue: {max elevation on path, row, col} priority_queue<tuple<int,int,int>, vector<tuple<int,int,int>>, greater<>> pq; // visited array to avoid revisiting cells vector<vector<bool>> visited(n, vector<bool>(n, false)); // push the starting cell (0,0) into the priority queue pq.emplace(grid[0][0], 0,0); visited[0][0] = true; // explore the grid while(!pq.empty()) { auto [current_max, row, col] = pq.top(); pq.pop(); // if we reach the bottom-right corner, return the current max elevation if(row == n-1 && col == n-1) return current_max; // explore all 4 possible directions for(const auto& [dx, dy] : directions) { int newRow = row + dx; int newCol = col + dy; // check bounds and if the cell is already visited if(newRow >= 0 && newRow < n && newCol >= 0 && newCol < n && !visited[newRow][newCol]) { visited[newRow][newCol] = true; // add the new cell to the queue qith the updated max elevation pq.emplace(max(current_max, grid[newRow][newCol]), newRow, newCol); } } } return -1; }};
💡 Approach 2 : Disjoint Set (Union-Find)
treat the grid as a set of connected components, where the idea is to progressively "flood" the grid by increasing T, connecting accessible cells into a single component
- sort all the cells by their elevation
- gradually process the cells in increasing order of elevation, connecting them to their neighbours using a union-find data structure
- stop when (0,0) and (n-1, n-1) belong to the same connected component
⌛ Complexity Analysis
TC: O(n^2 α (n^2)), where α is the inverse ackermann function (nearly constant in practice)
💻 Implementation of Solution
class DSU { vector<int> parent; vector<int> rank;public: DSU(int n) { parent.resize(n); rank.resize(n,0); for(int i=0; i < n; i++) { parent[i] = i; } } // find operation with path compression int find(int x) { if(parent[x] != x) { parent[x] = find(parent[x]); } return parent[x]; } void unite(int x, int y) { int rootX = find(x); int rootY = find(y); if(rootX != rootY) { if (rank[rootX] > rank[rootY]) { parent[rootY] = rootX; } else if (rank[rootX] < rank[rootY]) { parent[rootX] = rootY; } else { parent[rootY] = rootX; rank[rootX]++; } } }};class Solution {public: // function to convert 2D grid coordinates to 1D index int toIndex(int row, int col, int n) { return row * n + col; } int swimInWater(vector<vector<int>>& grid) { int n = grid.size(); // step 1: flatten the grid into a list of {elevation, row, col} vector<tuple<int,int,int>> cells; for(int row = 0; row < n; row++) { for(int col = 0; col < n; col++) { cells.emplace_back(grid[row][col], row, col); } } // step 2: sort the cells by elevation sort(cells.begin(), cells.end()); // step 3. initialise the DSU for all grid cells DSU dsu(n * n); // directions for movement: up, down, left, right const vector<pair<int, int>> directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // step 4. process cells in increasing order of elevation for(const auto& [elevation, row, col] : cells) { for(const auto& [dx, dy] : directions) { int newRow = row + dx; int newCol = col + dy; // check bounds if (newRow >= 0 && newRow < n && newCol >= 0 && newCol < n) { // If the neighbor has been processed, unite the current cell with the neighbor if (grid[newRow][newCol] <= elevation) { dsu.unite(toIndex(row, col, n), toIndex(newRow, newCol, n)); } } } // step 5. check if the top-left and bottom-right are connected if(dsu.find(0) == dsu.find(toIndex(n-1, n-1, n))) { return elevation; } } return -1; }};