Posted on

Description

Submission

class Solution {
public:
    int minJumps(vector<int>& arr) {
        int n = arr.size();
        if(n == 1) return 0;

        

        unordered_map<int, vector<int>> indices;

        for(int i = 0; i < n; ++i) {
            indices[arr[i]].push_back(i);
        }

        vector<int> visited(n, 0);

        queue<int> q;
        q.push(0);
        visited[0] = 1;
        int steps = 0;

        while(!q.empty()) {
            int cnt = q.size();

            while(cnt--) {
                int cur = q.front();
                q.pop();

                if(cur+1 < n && !visited[cur+1]) {
                    q.push(cur+1);
                    visited[cur+1] = 1;
                }

                if(cur-1 >= 0 && !visited[cur-1]) {
                    q.push(cur-1);
                    visited[cur-1] = 1;
                }

                for(int x: indices[arr[cur]]) {
                    if(visited[x]) continue;
                    q.push(x);
                    visited[x] = 1;
                }

                indices.erase(arr[cur]);
            }

            steps += 1;

            if (visited[n-1] == 1)
                return steps;
        }

        return -1;
    }
};

Leave a Reply

Your email address will not be published. Required fields are marked *