This is one of those problems where the clean idea matters more than the amount of code. For 778. Swim in Rising Water, the solution in this repository is mainly a heap / priority queue solution.
Guide
What?
The first job is to translate the English prompt into state, transition, and stopping conditions. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: heap / priority queue, graph traversal, binary search, two pointers.
The notes already sitting in the source point us in the right direction:
- bfs + binary search
Guide
When?
This pattern shows up when the brute force version has too many repeated checks, too many possible branches, or too much bookkeeping to do by hand. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are validPos, connect, swimInWater, dfs, valid.
Guide
Why?
The point of the implementation is not to make the code longer. It is to avoid doing the same thinking twice.
- A set is doing the membership or uniqueness work, which keeps the main loop readable.
- The queue gives the solution a level-by-level or frontier-style traversal.
- The heap keeps the best candidate available without sorting the whole world every time.
- The two-dimensional vector is the memory of the solution: grid state, DP state, or adjacency shape.
Guide
How?
Walk through the solution in this order:
- Start from the smallest reliable state.
- Expand one legal move at a time.
- Cache, count, or merge information as soon as it becomes settled.
- Let the final stored value answer the original question.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: O(n) to O(n log n), depending on the dominant loop or data structure operation
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01//bfs + binary search
02//Runtime: 1020 ms, faster than 5.16% of C++ online submissions for Swim in Rising Water.
03//Memory Usage: 63.2 MB, less than 5.00% of C++ online submissions for Swim in Rising Water.
04class Solution {
05public:
06 bool validPos(int i, int j, int m, int n){
07 return i >= 0 && i < m && j >= 0 && j < m;
08 };
09
10 bool connect(vector<vector<int>>& grid, int t){
11 // cout << "time: " << t << endl;
12 queue<vector<int>> q;
13 set<vector<int>> connected;
14
15 int m = grid.size(), n = grid[0].size();
16 q.push(vector<int>{0,0});
17 connected.insert({0,0});
18
19 vector<vector<int>> dirs = {{0,1}, {0,-1}, {1,0}, {-1,0}};
20
21 int count = 0;
22 //bfs
23 while(!q.empty()){
24 vector<int> node = q.front(); q.pop();
25
26 for(vector<int>& dir : dirs){
27 int ni = node[0]+dir[0], nj = node[1]+dir[1];
28 vector<int> nbr = {ni, nj};
29 //not valid position
30 if(!validPos(ni, nj, m, n)) continue;
31 //already visited
32 if(connected.find(nbr) != connected.end()) continue;
33 //water is over nbr
34 if(grid[ni][nj] <= t){
35 // cout << "(" << ni << ", " << nj << "): " << grid[ni][nj] << " | ";
36 q.push({ni, nj});
37 if(nbr[0] == m-1 && nbr[1] == n-1){
38 // cout << endl;
39 return true;
40 }
41 connected.insert(nbr);
42 }
43 }
44
45 count++;
46 }
47 // cout << endl;
48 return false;
49 };
50
51 int swimInWater(vector<vector<int>>& grid) {
52 int m = grid.size();
53 int n = grid[0].size();
54
55 int right = 0;
56 for(int i = 0; i < m; i++){
57 for(int j = 0; j < n; j++){
58 right = max(right, grid[i][j]);
59 }
60 }
61
62 int left = max(grid[0][0], grid[m-1][n-1]);
63 int mid;
64
65 //binary search, find left boundary
66 while(left <= right){
67 mid = left + (right-left)/2;
68 if(connect(grid, mid)){
69 right = mid-1;
70 }else{
71 left = mid+1;
72 }
73 }
74 // cout << endl;
75 if(left == m*n) return -1;
76 return left;
77 }
78};
79
80//dfs + binary search
81//https://leetcode.com/problems/swim-in-rising-water/discuss/113758/C%2B%2B-two-solutions-Binary-Search%2BDFS-and-Dijkstra%2BBFS-O(n2logn)-11ms
82//Runtime: 32 ms, faster than 76.63% of C++ online submissions for Swim in Rising Water.
83//Memory Usage: 10.1 MB, less than 50.00% of C++ online submissions for Swim in Rising Water.
84class Solution {
85 bool validPos(int i, int j, int n){
86 return i >= 0 && i < n && j >= 0 && j < n;
87 };
88
89 bool dfs(vector<vector<int>>& grid, vector<vector<int>>& dirs, vector<vector<bool>>& visited, int t, int i, int j){
90 int n = grid.size();
91 for(vector<int>& dir : dirs){
92 int ni = i+dir[0];
93 int nj = j+dir[1];
94 if(validPos(ni, nj, n) && !visited[ni][nj] && grid[ni][nj] <= t){
95 visited[ni][nj] = true;
96 if(ni == n-1 && nj == n-1) return true;
97 if(dfs(grid, dirs, visited, t, ni, nj)) return true;
98 }
99 }
100 return false;
101 };
102
103 bool valid(vector<vector<int>>& grid, int t){
104 int n = grid.size();
105 vector<vector<bool>> visited(n, vector(n, false));
106 visited[0][0] = true;
107 vector<vector<int>> dirs = {{0,1},{0,-1},{1,0},{-1,0}};
108 return dfs(grid, dirs, visited, t, 0, 0);
109 };
110public:
111 int swimInWater(vector<vector<int>>& grid) {
112 int n = grid.size();
113
114 int left = max(grid[0][0], grid[n-1][n-1]);
115 int right = n*n-1; //grid is a permutation of [0,...,n*n-1]
116 int mid;
117
118 while(left <= right){
119 mid = left + (right-left)/2;
120 if(valid(grid, mid)){
121 right = mid-1;
122 }else{
123 left = mid+1;
124 }
125 }
126
127 return left;
128 }
129};
130
131//Dijkstra using Priority Queue
132//https://leetcode.com/problems/swim-in-rising-water/discuss/113758/C%2B%2B-two-solutions-Binary-Search%2BDFS-and-Dijkstra%2BBFS-O(n2logn)-11ms
133//Runtime: 108 ms, faster than 16.72% of C++ online submissions for Swim in Rising Water.
134//Memory Usage: 11.3 MB, less than 25.00% of C++ online submissions for Swim in Rising Water.
135//time: O(N^2logN), space: O(N^2)
136class Solution {
137 bool validPos(int i, int j, int n){
138 return i >= 0 && i < n && j >= 0 && j < n;
139 };
140public:
141 int swimInWater(vector<vector<int>>& grid) {
142 int n = grid.size();
143
144 vector<vector<bool>> visited(n, vector(n, false));
145
146 vector<vector<int>> dirs = {{0,1},{0,-1},{1,0},{-1,0}};
147 //the smaller the earlier be popped
148 priority_queue<vector<int>, vector<vector<int>>, greater<vector<int>>> pq;
149
150 pq.push({grid[0][0], 0, 0});
151 visited[0][0] = true;
152
153 int ans = max(grid[0][0], grid[n-1][n-1]);
154
155 //visit node in increasing height order
156 while(!pq.empty()){
157 vector<int> node = pq.top(); pq.pop();
158 int i = node[1], j = node[2];
159 //update ans when we actually visit the node
160 ans = max(ans, node[0]);
161 // visited[i][j] = true;
162 for(vector<int>& dir : dirs){
163 int ni = i+dir[0];
164 int nj = j+dir[1];
165 if(validPos(ni, nj, n) && !visited[ni][nj]){
166 if(ni == n-1 && nj == n-1) return ans;
167 //here mark neighbor as visited just to avoid it be added to pq again
168 visited[ni][nj] = true;
169 pq.push({grid[ni][nj], ni, nj});
170 }
171 }
172 }
173
174 return ans;
175 }
176};
177
178//Dijkstra using Priority Queue + bfs speed up
179//https://leetcode.com/problems/swim-in-rising-water/discuss/113758/C%2B%2B-two-solutions-Binary-Search%2BDFS-and-Dijkstra%2BBFS-O(n2logn)-11ms
180//Runtime: 36 ms, faster than 66.21% of C++ online submissions for Swim in Rising Water.
181//Memory Usage: 11.3 MB, less than 25.00% of C++ online submissions for Swim in Rising Water.
182class Solution {
183 bool validPos(int i, int j, int n){
184 return i >= 0 && i < n && j >= 0 && j < n;
185 };
186public:
187 int swimInWater(vector<vector<int>>& grid) {
188 int n = grid.size();
189
190 vector<vector<bool>> visited(n, vector(n, false));
191
192 vector<vector<int>> dirs = {{0,1},{0,-1},{1,0},{-1,0}};
193 //the smaller the earlier be popped
194 priority_queue<vector<int>, vector<vector<int>>, greater<vector<int>>> pq;
195
196 pq.push({grid[0][0], 0, 0});
197 visited[0][0] = true;
198
199 int ans = max(grid[0][0], grid[n-1][n-1]);
200
201 //visit node in increasing height order
202 while(!pq.empty()){
203 vector<int> node = pq.top(); pq.pop();
204 int i = node[1], j = node[2];
205 //update ans when we actually visit the node
206 ans = max(ans, node[0]);
207 //the bfs queue is used to visit all connected node whose height <= ans
208 queue<vector<int>> bfsq;
209 bfsq.push({i, j});
210
211 while(!bfsq.empty()){
212 node = bfsq.front(); bfsq.pop();
213 int i = node[0], j = node[1];
214 // if(i == n-1 && j == n-1) return ans;
215
216 for(vector<int>& dir : dirs){
217 int ni = i+dir[0];
218 int nj = j+dir[1];
219 if(validPos(ni, nj, n) && !visited[ni][nj]){
220 if(ni == n-1 && nj == n-1) return ans;
221 //here mark neighbor as visited just to avoid it be added to pq again
222 visited[ni][nj] = true;
223 if(grid[ni][nj] <= ans){
224 //can be visited while ans is not updated
225 bfsq.push({ni, nj});
226 }else{
227 //must be visited after ans is updatd
228 pq.push({grid[ni][nj], ni, nj});
229 }
230 }
231 }
232 }
233 }
234
235 return ans;
236 }
237};Cost
Complexity
Time
O(n) to O(n log n), depending on the dominant loop or data structure operation
Dominated by the main traversal, recursion, or data-structure operations in the code.
Space
O(n) in the usual case for auxiliary containers or recursion
Auxiliary state plus the answer structure where the problem requires one.