BFS: Jump Game IV

Using pair to record the index and depth

const int N = 5e4 + 10;
int f[N];
class Solution {
public:
int minJumps(vector<int>& arr) {
memset(f, 0, sizeof(f));
const int n = arr.size();
if (n == 1) return 0;
unordered_map<int, vector<int>> m;
for (int i = 0; i < n; ++i) {
//if (i >= 1 && i < n -1 && arr[i-1] == arr[i] && arr[i] == arr[i+1]) continue;
m[arr[i]].push_back(i);
}
deque<pair<int, int>> dq;
dq.emplace_back(n-1, 0);
int ret = 0;
while (true) {
auto [k, depth] = dq.front();dq.pop_front();
if (k == 0) {
return depth;
}
for (auto &x: m[arr[k]]) {
if (x != k && !f[x]) {
f[x] = 1;
if (x == 0) return depth + 1;
dq.emplace_back(x, depth + 1);
}
}
for (auto di : {-1, 1}) {
if (k + di < n && k + di >= 0 && !f[k + di]) {
f[k + di] = 1;
if (k + di == 0) return depth + 1;
dq.emplace_back( k + di, depth + 1);
}
}
}
return ret;

}
};

A better way

const int N = 5e4 + 10;
bool f[N];
class Solution {
public:
int minJumps(vector<int>& arr) {
memset(f, 0, sizeof(f));
const int n = arr.size();
if (n==1) return 0;
unordered_map<int, vector<int>> m;
for (int i = 0; i < n; ++i) {
if (i >= 1 && i < n -1 && arr[i-1] == arr[i] && arr[i] == arr[i+1]) continue;
m[arr[i]].push_back(i);
}
deque<int> dq;
dq.emplace_back(n-1);
int ret = 0;
int depth = 1;
f[n-1] = true;
while (true) {
int sz = dq.size();
for (int i = 0; i < sz; ++i) {
int k = dq.front(); dq.pop_front();
if (k == 0) return depth;
for (auto &x: m[arr[k]]) {
if (x != k && !f[x]) {
f[x] = true;
if (x == 0) return depth;
dq.push_back(x);
}
}
for (auto di : {-1, 1}) {
if (k + di < n && k + di >= 0 && !f[k + di]) {
f[k + di] = true;
if (k + di == 0) return depth;
dq.push_back(k + di);
}
}
}
depth++;
}

return ret;
}
};

--

--

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