You are given an integer array nums of length n. You start at index 0, and your goal is to reach index n - 1. From any index i, you may perform one of the following operations: Adjacent Step: Jump to index i + 1 or i - 1, if the index is within bo

minJumps.js

/**
 * @param {number[]} nums
 * @return {number}
 */
var minJumps = function(nums) {
    const n = nums.length;
    if (n === 1) return 0;

    // 1. Build SPF (smallest prime factor) up to max(nums)
    const maxVal = Math.max(...nums);
    const spf = Array(maxVal + 1).fill(0);
    for (let i = 2; i <= maxVal; i++) {
        if (spf[i] === 0) {
            spf[i] = i;
            if (i * i <= maxVal) {
                for (let j = i * i; j <= maxVal; j += i) {
                    if (spf[j] === 0) spf[j] = i;
                }
            }
        }
    }

    // Helper: check primality using SPF
    const isPrimeVal = new Array(maxVal + 1).fill(false);
    for (let x = 2; x <= maxVal; x++) {
        if (spf[x] === x) isPrimeVal[x] = true;
    }

    // 2. Build buckets: prime p -> list of indices whose value is divisible by p
    const bucket = {};
    for (let i = 0; i < n; i++) {
        let x = nums[i];
        while (x > 1) {
            const p = spf[x];
            if (!bucket[p]) bucket[p] = [];
            bucket[p].push(i);
            while (x % p === 0) x /= p;
        }
    }

    // 3. BFS over indices
    const visited = Array(n).fill(false);
    const queue = [[0, 0]]; // [index, distance]
    let head = 0;
    visited[0] = true;

    while (head < queue.length) {
        const [i, dist] = queue[head++];

        if (i === n - 1) return dist;

        // Adjacent moves
        for (const nxt of [i - 1, i + 1]) {
            if (nxt >= 0 && nxt < n && !visited[nxt]) {
                visited[nxt] = true;
                queue.push([nxt, dist + 1]);
            }
        }

        // Prime teleportation
        const val = nums[i];
        if (val <= maxVal && isPrimeVal[val]) {
            const p = val;
            const list = bucket[p];
            if (list) {
                for (const j of list) {
                    if (!visited[j]) {
                        visited[j] = true;
                        queue.push([j, dist + 1]);
                    }
                }
                bucket[p] = null; // clear after use
            }
        }
    }


    return -1; // per constraints, shouldn't happen
};