leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

1345.cpp (1263B)

      1 class Solution {
      2   public:
      3     int minJumps(vector<int> &arr) {
      4         if (arr.size() < 2) return 0;
      5         if (arr.front() == arr.back()) return 1;
      6 
      7         unordered_map<int, vector<int>> um;
      8         unordered_set<int> visited;
      9         int n = arr.size();
     10 
     11         for (int i = 0; i < n; i++)
     12             um[arr[i]].push_back(i);
     13 
     14         queue<int> q;
     15         q.push(0);
     16         visited.insert(0);
     17         for (int lvl = 0; !q.empty(); lvl++) {
     18             for (int k = q.size(); k > 0; k--) {
     19                 int crnt = q.front();
     20                 q.pop();
     21 
     22                 if (crnt == n - 1) return lvl;
     23 
     24                 if (crnt + 1 < n && !visited.count(crnt + 1)) {
     25                     visited.insert(crnt + 1);
     26                     q.push(crnt + 1);
     27                 }
     28 
     29                 if (crnt - 1 >= 0 && !visited.count(crnt - 1)) {
     30                     visited.insert(crnt - 1);
     31                     q.push(crnt - 1);
     32                 }
     33 
     34                 for (int index : um[arr[crnt]]) {
     35                     if (!visited.count(index)) {
     36                         visited.insert(index);
     37                         q.push(index);
     38                     }
     39                 }
     40 
     41                 um[arr[crnt]].clear();
     42             }
     43         }
     44         return -1;
     45     }
     46 };