1306. Jump Game III

題目 / Problem

中文

給定一個由非負整數組成的陣列 arr，你一開始站在索引 start。當你位於索引 i 時，可以跳到 i + arr[i] 或 i - arr[i]（但不能跳出陣列邊界）。請判斷你是否能到達任何值為 0 的索引。

English

You are given an array of non-negative integers arr and a starting index start. From any index i, you may jump to either i + arr[i] or i - arr[i], but you may never jump outside the array. Return true if you can reach any index whose value is 0.

Constraints - 1 <= arr.length <= 5 * 10^4 - 0 <= arr[i] < arr.length - 0 <= start < arr.length

Example

Input:  arr = [4,2,3,0,3,1,2], start = 5
Output: true
Explanation: 5 -> 4 -> 1 -> 3 (value 0). ✅

名詞解釋 / Glossary

• DFS (Depth-First Search) / 深度優先搜尋：一種圖/樹的搜尋策略，沿著一條路徑一直走到底，走不下去才回頭嘗試別條路。通常用遞迴實作。 / A graph search strategy that follows one path as far as possible before backtracking. Usually implemented with recursion.
• BFS (Breadth-First Search) / 廣度優先搜尋：另一種搜尋策略，一層一層擴張，先看所有距離 1 的節點，再看距離 2 的，依此類推。通常用 queue 實作。 / A search strategy that expands layer by layer, visiting all nodes at distance 1, then distance 2, etc. Usually implemented with a queue.
• Visited set / 已訪問集合：紀錄哪些位置已經走過，避免無窮迴圈（例如 1 → 3 → 1 → 3 → …）。本題我們會用一個布林陣列或就地修改 arr 本身來標記。 / A record of positions already explored so we don't loop forever. We can use a boolean array, or mark arr in place.
• In-place marking / 原地標記：直接改寫輸入陣列來省下額外記憶體。本題的小技巧：把走過的位置加上一個 arr 不可能出現的數（例如負號），就能判斷是否走過。 / Mutating the input array itself to save memory. Trick here: negate the value at a visited index since values are guaranteed non-negative.
• Queue / 佇列：先進先出的資料結構，BFS 的核心。C++ 用 std::queue，C 通常用陣列加兩個索引模擬。 / A first-in-first-out container, the backbone of BFS. std::queue in C++; an array with two indices in C.
• Recursion / 遞迴：函式呼叫自己。DFS 寫成遞迴最直覺，但要小心呼叫深度（本題 n ≤ 5·10^4，遞迴深度勉強可接受）。 / A function calling itself. DFS reads naturally as recursion, but watch the call-stack depth.

思路

我們可以把這題想成一張圖：每個索引 i 是一個節點，且從 i 可以走到 i + arr[i] 與 i - arr[i] 兩個鄰居（若在邊界內）。問題就變成：「從 start 出發，能不能走到任何值為 0 的節點？」這就是經典的圖連通性搜尋，BFS 或 DFS 都能解。一個天真的想法是窮舉所有路徑，但路徑可能形成環（例如 1 → 3 → 1 → 3 …），會無限遞迴。關鍵的洞見是：每個索引最多只需要訪問一次，因為從同一個索引出發後續走法完全相同，重複訪問不會帶來新資訊。所以我們用一個「已訪問」標記避免回頭走。為了省記憶體，可以把走過的 arr[i] 取負（題目保證原值非負，所以負號是個合法的「已訪問」訊號）。複雜度因此是 O(n)，每個位置最多進 queue 一次。本範例選擇 BFS（如 hint 建議），用 queue 一層一層擴張，遇到值為 0 的位置就立刻回傳 true；queue 清空都沒找到就回傳 false。

Model the array as a graph: each index i is a node with up to two outgoing edges, to i + arr[i] and i - arr[i]. The question reduces to: starting from start, can we reach any node whose value is 0? Classic graph reachability — either BFS or DFS works. A naive "try all paths" approach explodes because of cycles (e.g. 1 → 3 → 1 → 3 …), so the key invariant is visit each index at most once: revisiting a node never reveals anything new, since the set of reachable nodes from it is fixed. We track visited indices to enforce that. To save space, we negate arr[i] in place — values are guaranteed non-negative, so a negative value is an unambiguous "already visited" flag. That gives O(n) time, since every index enters the queue at most once. Following the hint, we use BFS: push start, then repeatedly pop a position, check if its value is 0 (success!), and otherwise enqueue its two neighbors (if in-bounds and unvisited). If the queue drains without success, the answer is false.

逐步走查 / Walkthrough

Example: arr = [4,2,3,0,3,1,2], start = 5. Initially nothing visited.

走查重點 / Key takeaways: 出隊時才檢查是否為 0（也可入隊時就檢查，效果一樣）；負號既是「已訪問」旗標也順便保留原始絕對值，方便取出時用 abs() 還原。 / We check for 0 on pop (checking on push works too). The negative sign doubles as a visited flag while preserving the magnitude via abs().

Solution — C

// 演算法 / Algorithm:
// 用 BFS 從 start 開始一層一層擴張，每個索引最多訪問一次。
// 走過的位置把 arr[i] 取負當作「已訪問」標記（原值非負，所以負號獨一無二）。
// BFS expands layer by layer from start; each index is visited at most once.
// We mark visited indices by negating arr[i] (values are non-negative, so negative = visited).

#include <stdbool.h>   // 引入 bool 型別 / brings in the bool type
#include <stdlib.h>    // 引入 malloc / free / abs / for malloc, free, abs

bool canReach(int* arr, int arrSize, int start) {
    // 邊界檢查：起點本身就是 0 直接回傳 true / Edge case: start is already 0.
    if (arr[start] == 0) return true;

    // 用一個整數陣列當 queue；最壞情況每個索引都進隊一次，所以大小 arrSize 就夠。
    // Use an int array as a queue; worst case each index enters once, so arrSize suffices.
    int* queue = (int*)malloc(sizeof(int) * arrSize);
    int head = 0, tail = 0;            // head 是讀取位置，tail 是寫入位置 / read & write indices

    queue[tail++] = start;             // 把起點放進 queue / enqueue the start index
    arr[start] = -arr[start];          // 立即標記已訪問（取負）/ mark visited by negating

    // 主迴圈：當 queue 還有東西就繼續 / Main loop: while the queue isn't empty.
    while (head < tail) {
        int i = queue[head++];         // 取出隊首索引 / pop the front index
        int step = -arr[i];            // 取出原始跳躍距離（之前取了負，再取負還原）/ recover original jump distance
                                       // 注意：因為已經訪問過，arr[i] 一定是負的 / arr[i] is negative here

        // 嘗試往右跳 / Try jumping right.
        int right = i + step;
        if (right < arrSize) {         // 不能跳出右邊界 / must stay in bounds
            if (arr[right] == 0) {     // 找到 0 ⇒ 成功 / found a zero ⇒ success
                free(queue);
                return true;
            }
            if (arr[right] > 0) {      // 還沒訪問過（值仍為正）/ not visited yet (still positive)
                arr[right] = -arr[right];   // 標記已訪問 / mark visited
                queue[tail++] = right;       // 入隊 / enqueue
            }
        }

        // 嘗試往左跳 / Try jumping left.
        int left = i - step;
        if (left >= 0) {               // 不能跳出左邊界 / must stay in bounds
            if (arr[left] == 0) {      // 找到 0 ⇒ 成功 / found a zero ⇒ success
                free(queue);
                return true;
            }
            if (arr[left] > 0) {       // 還沒訪問過 / not visited yet
                arr[left] = -arr[left];     // 標記 / mark
                queue[tail++] = left;        // 入隊 / enqueue
            }
        }
    }

    free(queue);                       // 記得釋放動態記憶體 / always free what you malloc
    return false;                      // queue 清空仍沒找到 0 / drained without finding 0
}

Solution — C++

// 演算法 / Algorithm:
// 同 C 版本：BFS 從 start 出發，每個索引最多訪問一次，
// 用 std::queue<int> 管理待處理索引，原地把 arr[i] 取負作為已訪問旗標。
// Same as the C version: BFS from start, each index visited at most once,
// using std::queue<int> as the worklist and in-place negation of arr[i] as the visited flag.

#include <vector>      // std::vector
#include <queue>       // std::queue
#include <cstdlib>     // std::abs

class Solution {
public:
    bool canReach(std::vector<int>& arr, int start) {
        const int n = arr.size();         // 取得陣列大小 / cache the array size
        if (arr[start] == 0) return true; // 起點就是 0 直接成功 / start itself is a zero

        std::queue<int> q;                // BFS 用的 queue（先進先出）/ FIFO worklist for BFS
        q.push(start);                    // 入隊起點 / enqueue the start
        arr[start] = -arr[start];         // 標記已訪問（取負）/ mark visited by negation

        while (!q.empty()) {              // 還有待處理索引就繼續 / loop until queue drains
            int i = q.front();            // 取隊首 / peek front
            q.pop();                      // 移除隊首 / remove front
            int step = -arr[i];           // 還原原始跳躍距離 / recover original jump distance

            // lambda：嘗試訪問鄰居 j。若 j 是 0 回傳 true；若可訪問則標記並入隊。
            // Lambda: try visiting neighbor j. Returns true if j is a zero (success).
            // Captures by reference so it can read/modify arr and q.
            auto visit = [&](int j) -> bool {
                if (j < 0 || j >= n) return false;   // 出界 / out of bounds
                if (arr[j] == 0) return true;        // 找到 0 / hit a zero
                if (arr[j] > 0) {                    // 還沒訪問過 / unvisited
                    arr[j] = -arr[j];                // 標記 / mark visited
                    q.push(j);                       // 入隊 / enqueue
                }
                return false;                        // 還沒找到 0 / not a success yet
            };

            if (visit(i + step)) return true;        // 試右跳 / try right jump
            if (visit(i - step)) return true;        // 試左跳 / try left jump
        }

        return false;                                // queue 空了還沒找到 / no zero reachable
    }
};

複雜度 / Complexity

• Time: O(n) — 每個索引最多進 queue 一次（因為訪問後就被標記為負，不再重複入隊），每次處理 O(1) 個鄰居。n 是陣列長度 arr.length。 / Each index is enqueued at most once thanks to the visited flag, and each pop processes O(1) neighbors. n is the array length.
• Space: O(n) — 最壞情況 queue 可能同時裝下所有索引。我們透過原地修改 arr 省下了額外的 visited 陣列。 / In the worst case the queue can hold all n indices. We avoid an extra visited array by reusing arr in place.

Pitfalls & Edge Cases

• 無窮迴圈 / Infinite loop：若不標記已訪問，從 i 跳到 j 再跳回 i 會無限循環。負號標記是這個演算法的核心安全網。 / Without a visited flag you'll bounce between two indices forever. The negation trick is the safety net.
• 起點就是 0 / Start is already zero：要在最開頭檢查 arr[start] == 0，否則我們會把它取負成 -0 == 0，邏輯仍然正確，但提早回傳更乾淨。 / Handle arr[start] == 0 up front; negating zero is still zero so it would still work, but an early return is cleaner.
• arr[i] == 0 的位置 / Indices whose value is 0：這些是目標，不要取負（負 0 還是 0，但流程上我們從不把 0 入隊，因為一發現就回傳 true）。 / Zero-valued indices are goals; we never enqueue them — we return true the moment we see one.
• 越界 / Out-of-bounds jumps：i + arr[i] 可能 ≥ n，i - arr[i] 可能 < 0，必須先檢查再存取，否則 C 的未定義行為或 C++ 的 segfault 就出現了。 / Always bounds-check before indexing — out-of-range reads are undefined behavior in C and likely crashes in C++.
• 原地修改的副作用 / Mutating the input：本解法會永久改變 arr（值變成負的）。在面試或實務中若不被允許，請改用獨立的 visited 布林陣列。 / This solution mutates arr. If the caller can't accept that, use a separate std::vector<bool> visited(n) instead.
• 遞迴 DFS 的棧深度 / Recursion depth for DFS：n 可達 5·10^4，純遞迴 DFS 在某些環境下可能爆棧；BFS 用 queue 就沒這風險。 / A purely recursive DFS could blow the stack at n = 5·10^4 on some platforms; iterative BFS sidesteps that.