1345. Jump Game IV

題目 / Problem

中文： 給定整數陣列 arr，你一開始站在索引 0。每一步可以從索引 i 跳到： - i + 1（若 i + 1 < arr.length） - i - 1（若 i - 1 >= 0） - 任何 j，只要 arr[i] == arr[j] 且 i != j

求跳到最後一個索引 arr.length - 1 所需的最少步數。

English: Given an integer array arr, you start at index 0. In one step you may jump from index i to: - i + 1 (if in bounds) - i - 1 (if in bounds) - any j such that arr[i] == arr[j] and i != j

Return the minimum number of steps to reach the last index.

Constraints / 限制 - 1 <= arr.length <= 5 * 10^4 - -10^8 <= arr[i] <= 10^8

Example / 範例

Input : arr = [100,-23,-23,404,100,23,23,23,3,404]
Output: 3
Explanation: 0 → 4 (same value 100) → 3 (same value 404 via the value-404 group) → 9

名詞解釋 / Glossary

BFS（廣度優先搜尋 / Breadth-First Search）：一層一層往外擴張的搜尋方式。從起點開始，先走完所有 1 步可達的節點，再走 2 步可達的，依此類推。第一次碰到目標的層數，就是最短步數。
Queue（佇列）/ FIFO：先進先出的資料結構。BFS 用它記錄「待處理」的節點。In C we simulate it with an array + two indices (head & tail); in C++ we use std::queue or just a vector with indices.
Hash map / 雜湊表（C++ unordered_map）：以 key 查 value 的常數時間結構。這題用 value → list of indices 把所有「相同值」的索引分群。
Visited 陣列 / visited array：記錄哪些索引已經被加入過 BFS 佇列，避免重複處理（重複處理會把 BFS 退化成指數爆炸）。
「圖」的抽象 / Graph view：把陣列每個索引想成一個節點，依照題目規則畫邊（i±1、相同值的對）。本題其實是在這張圖上找 0 → n-1 的最短路徑。
關鍵剪枝 / Key pruning trick：當我們第一次處理某個值的群組（例如所有等於 23 的索引）後，立刻清空這個群組。因為下一次再從另一個 23 出發時，群組裡的其他索引要嘛已經被訪問、要嘛已經在這一輪被加入；若不清空，遇到 [7,7,7,...,7] 這種輸入會掃成 O(n²) 而超時。

思路

最直覺的想法是「從索引 0 嘗試所有跳法的組合」，但這是指數級的搜尋，5×10⁴ 規模絕對 TLE。注意到題目要求最少步數（每步代價相同），這正是 BFS 的經典場景：把每個索引看成圖上的節點，i+1、i-1、以及所有 arr[j]==arr[i] 的 j 都是鄰居，從節點 0 做 BFS，第一次抵達節點 n-1 時的層數就是答案。為了能夠常數時間找到「所有跟我同值的索引」，先用一個雜湊表把 value → indices 列表 預先建好。最大的陷阱是：如果輸入裡有大量重複值（例如連續 50000 個 7），每處理一個 7 都重新掃整個 7 的群組，總共會做 O(n²) 次邊探索而 TLE。解法是「一次性消耗」：當我們從某個值的群組第一次跳出去後，把這個群組從表裡清空（或標記為空）。為什麼安全？因為這個群組裡所有索引在這一輪 BFS 結束時要嘛被訪問、要嘛已經進入佇列；後續任何人再透過同一個值跳，能跳到的目標都早已被處理，不會錯過更短的路徑。

The brute-force "try every jump combination" is exponential and dies immediately at n = 5×10⁴. Because every move costs exactly one step, this is a textbook shortest path with uniform edge weight, which is exactly what BFS solves. Model each index as a graph node with edges to i+1, i-1, and every j such that arr[i] == arr[j]; BFS from node 0 and return the level at which node n-1 is first dequeued. To find "all indices with the same value" in O(1) lookup, pre-build a hash map value → list of indices. The crucial trap is that a value with many duplicates (e.g. fifty thousand 7s) would, if revisited naively, cost O(n²) total edge expansions. The fix is consume the bucket exactly once: the first time BFS expands any index of value v, we visit every other index with the same value and then clear that bucket. This is safe because every index in the bucket either is already visited or gets enqueued in the same round — so no shorter path is ever lost, but no value-bucket is ever scanned twice. This collapses the overall work back down to O(n).

逐步走查 / Walkthrough

Example input: arr = [100,-23,-23,404,100,23,23,23,3,404], n = 10, target is index 9.

Preprocessing — 值 → 索引列表 / value → index list

value	indices
100	[0, 4]
-23	[1, 2]
404	[3, 9]
23	[5, 6, 7]
3	[8]

BFS starts with queue=[0], visited={0}, steps=0. We process the queue one full level at a time, incrementing steps after each level.

Level (steps before)	Pop	Neighbours discovered	Newly visited	Buckets cleared
0	`0`	`i+1=1`; same-value 100 → `4`	{1, 4}	100
1	`1`	`i+1=2`; `i-1=0`✓; same-value -23 → (2 not yet visited, add)	{2}	-23
1	`4`	`i+1=5`; `i-1=3`; same-value 100 already empty	{3, 5}	—
2	`2`	`i+1=3`✓; `i-1=1`✓; -23 bucket empty	—	—
2	`5`	`i+1=6`; `i-1=4`✓; same-value 23 → `7` (6 just added)	{6, 7}	23
2	`3`	`i+1=4`✓; `i-1=2`✓; same-value 404 → `9`	{9}	404
3	`6`	`i+1=7`✓; `i-1=5`✓; 23 empty	—	—
3	`7`	`i+1=8`; `i-1=6`✓; 23 empty	{8}	—
3	`9`	9 == n-1, return `steps = 3` ✓	—	—

(✓ means "already visited, skipped".) The answer 3 matches the expected output, and the path 0 → 4 → 3 → 9 is exactly the one the explanation cites.

Solution — C

// Algorithm: BFS over indices. Edges = (i-1, i+1, all j with arr[i]==arr[j]).
// Pre-build a hash map value -> indices. First time we expand any index of value v,
// enqueue every same-value index and then CLEAR that bucket so we never rescan it.
// Without this clearing, inputs like [7,7,...,7] would cost O(n^2) and TLE.

#include <stdio.h>     // 標準 I/O / standard I/O
#include <stdlib.h>    // malloc, calloc, free / 動態記憶體
#include <string.h>    // memset (備用 / just in case)

#define HASH_SIZE 100003                              // 質數桶數，降低碰撞 / prime bucket count, fewer collisions

// 雜湊表的一個節點：保存某個 value，以及所有等於該 value 的索引清單
// One hash-table node: stores a value and the list of indices that hold that value
typedef struct Bucket {
    int value;              // 鍵：陣列中的數值 / key: the integer value
    int *idx;               // 值：索引動態陣列 / dynamic array of indices
    int count;              // 目前有幾個索引 / current size
    int cap;                // 容量 / capacity for realloc
    struct Bucket *next;    // 同一個桶內的鏈結 / chaining for collisions
} Bucket;

// 簡單的整數雜湊：把 int 攪一攪後取模 / simple integer mix-then-mod hash
static int hashKey(int v) {
    unsigned int u = (unsigned int)v;                 // 轉成 unsigned 避免負數取模未定義 / avoid UB with negative %
    u = ((u >> 16) ^ u) * 0x45d9f3bU;                 // 經典 bit-mix / well-known mixing constant
    u = ((u >> 16) ^ u);                              // 再混一次 / mix again
    return (int)(u % HASH_SIZE);                      // 落到桶範圍 / map into bucket range
}

// 找到 value 對應的桶；若沒有就建立一個空桶 / find-or-create the bucket for `value`
static Bucket* getBucket(Bucket **table, int value) {
    int h = hashKey(value);                           // 算雜湊位置 / compute bucket index
    for (Bucket *b = table[h]; b != NULL; b = b->next) {  // 走訪鏈結尋找 / walk the chain
        if (b->value == value) return b;              // 命中現有桶 / cache hit
    }
    Bucket *b = (Bucket*)malloc(sizeof(Bucket));      // 配置新桶 / allocate new bucket
    b->value = value;                                 // 設定鍵 / set key
    b->cap = 4;                                       // 初始容量 4 / start with capacity 4
    b->count = 0;                                     // 還沒有索引 / no indices yet
    b->idx = (int*)malloc(sizeof(int) * b->cap);      // 配置索引陣列 / allocate index array
    b->next = table[h];                               // 頭插法接到鏈結最前面 / prepend to chain
    table[h] = b;                                     // 更新桶頭 / update bucket head
    return b;                                         // 回傳桶 / return bucket
}

// 把索引 i 加進 value 桶；必要時擴容 / append index `i` to its bucket, grow if needed
static void bucketPush(Bucket *b, int i) {
    if (b->count == b->cap) {                         // 滿了要擴容 / grow on full
        b->cap *= 2;                                  // 加倍 / double capacity
        b->idx = (int*)realloc(b->idx, sizeof(int) * b->cap);  // realloc 重新配置 / realloc to new size
    }
    b->idx[b->count++] = i;                           // 寫入並前移計數 / write and bump count
}

// 把整張表釋放掉，避免記憶體洩漏 / free the whole hash table
static void freeTable(Bucket **table) {
    for (int h = 0; h < HASH_SIZE; h++) {             // 走過每個桶頭 / walk every bucket
        Bucket *b = table[h];
        while (b != NULL) {                           // 釋放鏈結中的每個節點 / free chain
            Bucket *next = b->next;
            free(b->idx);                             // 先釋放內部陣列 / free inner array
            free(b);                                  // 再釋放節點本身 / then the node
            b = next;
        }
    }
    free(table);                                      // 最後釋放桶頭陣列 / free the bucket array itself
}

int minJumps(int* arr, int arrSize) {
    if (arrSize <= 1) return 0;                       // 起點就是終點，0 步 / start == end already

    // 1) 預先建立 value -> 索引列表 的雜湊表
    //    Build the value -> indices map.
    Bucket **table = (Bucket**)calloc(HASH_SIZE, sizeof(Bucket*));  // 全部初始化為 NULL / zero-initialised
    for (int i = 0; i < arrSize; i++) {               // 掃一遍陣列 / one pass over arr
        Bucket *b = getBucket(table, arr[i]);         // 取得對應的桶 / fetch the bucket
        bucketPush(b, i);                             // 把索引塞進去 / append the index
    }

    // 2) BFS 所需的 visited 陣列與佇列
    //    visited[] and a ring-free queue for BFS.
    char *visited = (char*)calloc(arrSize, sizeof(char));  // 0=未訪 1=已訪 / 0=unseen, 1=seen
    int *queue = (int*)malloc(sizeof(int) * arrSize); // 佇列容量最多 n（每點最多入隊一次）/ at most n enqueues
    int qHead = 0, qTail = 0;                         // 佇列頭尾指標 / head/tail indices
    queue[qTail++] = 0;                               // 把起點入隊 / enqueue start
    visited[0] = 1;                                   // 標記為已訪 / mark visited
    int steps = 0;                                    // 目前的層數 / current BFS level

    int answer = -1;                                  // 預設 -1，理論上一定會更新 / default fallback

    // 3) 一次處理一整層 / process one full BFS level per outer iteration
    while (qHead < qTail) {                           // 佇列還有東西就繼續 / while queue not empty
        int levelSize = qTail - qHead;                // 這一層有多少節點 / nodes in this level
        for (int s = 0; s < levelSize; s++) {         // 把這一層全部彈出處理 / pop them all
            int i = queue[qHead++];                   // 取出當前索引 / dequeue index

            if (i == arrSize - 1) {                   // 抵達終點就回答 / reached last index
                answer = steps;
                goto done;                            // 跳出兩層迴圈做清理 / break out for cleanup
            }

            // 鄰居 1：i+1 / neighbour i+1
            if (i + 1 < arrSize && !visited[i + 1]) {
                visited[i + 1] = 1;                   // 標記避免重複入隊 / mark to avoid re-enqueue
                queue[qTail++] = i + 1;               // 入隊 / enqueue
            }
            // 鄰居 2：i-1 / neighbour i-1
            if (i - 1 >= 0 && !visited[i - 1]) {
                visited[i - 1] = 1;
                queue[qTail++] = i - 1;
            }
            // 鄰居 3：所有跟 arr[i] 同值的 j / all j with arr[j] == arr[i]
            Bucket *b = getBucket(table, arr[i]);     // 取出該值的桶 / fetch the value's bucket
            for (int k = 0; k < b->count; k++) {      // 一次處理整桶 / walk the whole bucket
                int j = b->idx[k];
                if (!visited[j]) {                    // 沒訪過才加入 / only enqueue unseen
                    visited[j] = 1;
                    queue[qTail++] = j;
                }
            }
            b->count = 0;                             // 關鍵：清空桶，避免下次再掃 / KEY: empty the bucket
        }
        steps++;                                      // 整層處理完，步數 +1 / finished this level
    }

done:
    free(visited);                                    // 釋放 visited / free visited
    free(queue);                                      // 釋放佇列 / free queue
    freeTable(table);                                 // 釋放整張雜湊表 / free hash table
    return answer;                                    // 回傳最少步數 / return answer
}

Solution — C++

// Algorithm: BFS over array indices. Edges go to i-1, i+1, and every j with arr[i]==arr[j].
// Pre-build unordered_map<value, vector<int>>; after expanding any index of value v,
// clear that bucket so duplicate-value inputs don't blow up to O(n^2).

#include <vector>           // std::vector：動態陣列容器 / dynamic array
#include <queue>            // std::queue：FIFO 佇列 / FIFO queue
#include <unordered_map>    // 雜湊表，平均 O(1) 查詢 / hash map, O(1) average lookup

class Solution {
public:
    int minJumps(std::vector<int>& arr) {
        int n = (int)arr.size();                          // 取得長度 / array length
        if (n <= 1) return 0;                             // 起點就是終點 / start == end

        // value -> 該值所有出現位置 / value -> all indices where it occurs
        // unordered_map 用雜湊，平均 O(1) / unordered_map is a hash map
        std::unordered_map<int, std::vector<int>> sameVal;
        sameVal.reserve(n * 2);                           // 預留空間減少 rehash / pre-reserve to avoid rehashing
        for (int i = 0; i < n; ++i) {                     // 預處理：一次掃過 / single pass
            sameVal[arr[i]].push_back(i);                 // 把 i 加到對應的列表 / append i to its bucket
        }

        std::vector<char> visited(n, 0);                  // 用 char 當布林省空間 / use char as bool to save space
        std::queue<int> q;                                // BFS 佇列 / BFS queue
        q.push(0);                                        // 從索引 0 出發 / start from index 0
        visited[0] = 1;                                   // 標記為已訪 / mark visited
        int steps = 0;                                    // 當前層數 = 已走步數 / level == steps taken

        while (!q.empty()) {                              // 佇列空了就結束 / loop until empty
            int levelSize = (int)q.size();                // 這一層的節點數 / freeze the level boundary
            for (int s = 0; s < levelSize; ++s) {         // 處理整層 / process one full level
                int i = q.front();                        // 取出隊頭 / peek front
                q.pop();                                  // 彈出 / pop

                if (i == n - 1) return steps;             // 抵達終點 / reached the target

                // 鄰居 i+1 / right neighbour
                if (i + 1 < n && !visited[i + 1]) {
                    visited[i + 1] = 1;
                    q.push(i + 1);
                }
                // 鄰居 i-1 / left neighbour
                if (i - 1 >= 0 && !visited[i - 1]) {
                    visited[i - 1] = 1;
                    q.push(i - 1);
                }
                // 同值索引：用 auto& 取引用，避免複製整個 vector / take a reference, no copy
                auto& bucket = sameVal[arr[i]];
                for (int j : bucket) {                    // range-for：遍歷容器的語法糖 / range-based for loop
                    if (!visited[j]) {
                        visited[j] = 1;
                        q.push(j);
                    }
                }
                bucket.clear();                           // 關鍵剪枝：清空避免 O(n^2) / KEY pruning step
            }
            ++steps;                                      // 整層處理完才加一 / increment after finishing the level
        }
        return -1;                                        // 題目保證可達，理論不會到這 / unreachable per constraints
    }
};

複雜度 / Complexity

Time: O(n) — 預處理一次 O(n)；BFS 中每個索引最多入隊一次（被 visited 擋住），每條 i±1 邊只看常數次，而「同值邊」因為桶被清空，整個過程中所有桶加起來最多被走訪 n 次。因此總成本與 n 成線性。 Pre-processing is O(n); each index is enqueued at most once (guarded by visited); the i±1 edges contribute O(1) per node; and because every value bucket is consumed-and-cleared exactly once, the total work across all same-value expansions is O(n). Overall: linear in the array length.
Space: O(n) — 雜湊表存 n 個索引、visited 與佇列各 n。沒有遞迴堆疊。 The hash map stores all n indices, plus an O(n) visited array and an O(n) queue. No recursion stack.

Pitfalls & Edge Cases

沒有「一次性清空桶」 / Forgetting to clear the value bucket. 輸入像 [7,7,7,...,7]（n 個 7）時，每跳一次都會重掃整個桶，導致 O(n²) 並 TLE。解法是在第一次展開該值後立刻 bucket.clear()，因為此時整桶內的索引要嘛已 visited、要嘛已入隊。 / Without it, duplicate-heavy inputs degrade to O(n²).
在「入隊時」還是「出隊時」檢查終點 / Where to check i == n-1. 本題在出隊時檢查很乾淨：步數正好等於 BFS 層數。若在入隊時提早 return，記得回傳 steps + 1。 / Checking at dequeue keeps steps aligned with the BFS level; checking at enqueue must return steps + 1.
arrSize == 1 的邊界 / Single-element array. 起點就是終點，直接回傳 0；若沒處理，BFS 仍會正確回傳 0，但提前 return 更清楚也避免不必要的 allocation。 / Handle up front.
負數 % 不安全 / % on signed ints can be negative. arr[i] 範圍含 -10^8，自製雜湊請先轉 unsigned int 再運算，避免桶下標為負導致越界。 / Cast to unsigned before modulo.
visited 必要性 / Without visited BFS explodes. 沒有訪問標記時，BFS 會無限地重複放入舊節點。visited 必須在入隊那一刻就標記（不是出隊時），否則同一層內仍可能重複入隊。 / Mark visited at enqueue time, not dequeue time.
題目保證可達 / Target is always reachable. 因為 i+1 一定可走，所以最壞只是 n-1 步；不需要特別處理「無解」的回傳值，但程式裡留個 -1 fallback 比較安全。 / i+1 edges alone guarantee reachability, but a -1 fallback is good defensive practice.