Algorithm (BFS)

1. First, we build a graph $G=(V,E)$ where $V$ is the set of of indices of the input array which we denote as $A$. For each $i$ in $0,…,\mathrm{size}(A)$, there is an edge $e=(i,j)$ if

   1. $j=i+1\text{ and }i+1<n$
   2. $j=i-1$ and $i-1\geq0$
   3. $j\neq i$ and $A_{j}=A_{i}.$

2. The this problem is reduced to finding the shortest path between $v_{\mathrm{start}}=0$ and $v_{\mathrm{end}}=n-1,$ which could be solved using BFS.

3. If $A_{i:j}$ is of the pattern $[x,…,x],$ i.e. a subsequence containing only one unique element, we only build $e=(i,j)$ and ignore all the rest. One could prove that this does not affect the final result using an exchange argument and case analysis.

Code

class Solution {
 public:
  int minJumps(vector<int>& arr) {
    const auto n = size(arr);

    const auto value_group = [&](std::unordered_map<int, std::vector<int>> self = {}) {
      for (int i = 0; i < n; ++i) {
        if (i >= 1 and i + 1 < n and arr[i] == arr[i - 1] and arr[i] == arr[i + 1])
          continue;
        self[arr[i]].emplace_back(i);
      }
      return self;
    }();

    const auto G = [&](std::vector<std::vector<int>> self = {}) {
      self.assign(n, {});
      for (int i = 0; i < n; ++i) {
        if (i + 1 < n)
          self[i].emplace_back(i + 1);
        if (i - 1 >=0)
          self[i].emplace_back(i - 1);
      }
      for (const auto & [val, g] : value_group) 
        for (int i = 0; i < size(g); ++i) 
          for (int j = i + 1; j < size(g); ++j) 
              self[g[i]].emplace_back(g[j]), self[g[j]].emplace_back(g[i]);

      return self;
    }();

    const auto solution = [&] {
      const int target = n - 1;

      struct state_t {
        mutable std::deque<int> Q;
        mutable std::optional<int> D[50000];
      };

      for (auto state = state_t{{0}, {0}}; not empty(state.Q);) {
        const auto &[Q, D] = state;
        const auto cur_node = Q.front();
        Q.pop_front();
        if (cur_node == target)
          return D[cur_node].value();
        else {
          for (const auto neighbor : G[cur_node]) {
            if (not D[neighbor]) {
              D[neighbor] = D[cur_node].value() + 1;
              Q.emplace_back(neighbor);
            }
          }
        }
      }
      return -1;
    }();

    return solution;
  }
};