leetcode

0 class Solution {

1 public:

2 int minJumps(vector<int> &arr) {

3 if (arr.size() < 2) return 0;

4 if (arr.front() == arr.back()) return 1;

5

6 unordered_map<int, vector<int>> um;

7 unordered_set<int> visited;

8 int n = arr.size();

9

10 for (int i = 0; i < n; i++)

11 um[arr[i]].push_back(i);

12

13 queue<int> q;

14 q.push(0);

15 visited.insert(0);

16 for (int lvl = 0; !q.empty(); lvl++) {

17 for (int k = q.size(); k > 0; k--) {

18 int crnt = q.front();

19 q.pop();

20

21 if (crnt == n - 1) return lvl;

22

23 if (crnt + 1 < n && !visited.count(crnt + 1)) {

24 visited.insert(crnt + 1);

25 q.push(crnt + 1);

26 }

27

28 if (crnt - 1 >= 0 && !visited.count(crnt - 1)) {

29 visited.insert(crnt - 1);

30 q.push(crnt - 1);

31 }

32

33 for (int index : um[arr[crnt]]) {

34 if (!visited.count(index)) {

35 visited.insert(index);

36 q.push(index);

37 }

38 }

39

40 um[arr[crnt]].clear();

41 }

42 }

43 return -1;

44 }

45 };