My Mistakes

DFS coordinates

The problem and the correct solution can be found HERE.

class Solution {
public:
bool dfs(vector<vector<int>>& grid, int idx, int t, int N, unordered_set<int>& seen) {
vector<pair<int, int>> dirs = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};


int i = idx/N, j = idx % N;
if (i < 0 || i >= N || j < 0 || j >= N) return false;
if (grid[i][j] > t) return false;
if (idx == N*N - 1) return true;
if (seen.count(idx)) return false;
else {
seen.insert(idx);
for (auto [di, dj] : dirs) {
int new_idx = (i + di)*N + j + dj;
if (dfs(grid, new_idx, t, N, seen)) return true;
}
return false;
}
}
int swimInWater(vector<vector<int>>& grid) {
const int N = grid.size();
int lo = 0, hi = N * N - 1;
unordered_set<int> seen;
while (lo < hi) {
int mid = lo + (hi - lo)/2;
seen.clear();
if (dfs(grid, 0, mid, N, seen)) {
hi = mid;
}
else lo = mid + 1;
}
return lo;
}
};

The bug is in this line. I am not sure whether i+di, j+dj are valid or not. If they are not valid, we may generate valid new_idx and hence get wrong answer.

int new_idx = (i + di)*N + j + dj;

--

--

--

Data Scientist/MLE/SWE @takemobi

Love podcasts or audiobooks? Learn on the go with our new app.

Programming Architectures — Redux | ReSwift

What went well ?

Javascript Understanding Destructuring in ES6

GraphQL Dynamic Persisted Queries

[Java][Greedy][LeetCode]Non-overlapping Intervals #435

How to set up Redux with React

Difference between var and val

Flutter vs React Native: What to choose to build your mobile app in 2020? (developer insights)

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Jimmy Shen

Jimmy Shen

Data Scientist/MLE/SWE @takemobi

More from Medium

BACKTRACKING ALGORITHM

FOVO: The Fear of Voluntary Opportunities.

A lightbulb hovering above a hand — representing the idea of a ‘lightbulb moment’, where we think of a new idea and are open to this.

My OIBSIP Experience

Education and Freedom (Part 1)