// 演算法 / Algorithm:
// 貪婪 + BFS 分層思維。維護「目前這跳的右邊界 currentEnd」與「下一跳最遠能到 farthest」。
// Greedy with BFS-layer thinking. Track current-jump right boundary and the farthest
// reachable if we made one more jump. When i hits currentEnd, commit a jump.
// Time O(n), Space O(1).

#include <stdio.h>   // 標準 I/O，用於本機測試 / standard I/O for local testing

// 簡單的 max 巨集 / simple max macro
#define MAX(a, b) ((a) > (b) ? (a) : (b))
//                ^ 三元運算子: 如果 a>b 取 a，否則取 b
//                ^ ternary: pick a if a>b, else b

int jump(int* nums, int numsSize) {
    // numsSize 是陣列長度 n / numsSize is the array length n
    // nums 是一個 int* (指向陣列首元素的指標) / nums is an int* (pointer to first element)

    int jumps = 0;        // 已跳次數 / number of jumps taken so far
    int currentEnd = 0;   // 目前這一跳能到達的最右 index / right boundary of current jump layer
    int farthest = 0;     // 下一跳最遠能到達的 index / farthest reachable in one more jump

    // 只掃到 n-2 (含)。若 i 走到 n-1，就代表已經在終點，不需再起跳。
    // Loop only to n-2. If i reached n-1, we're already at the goal; no more jumps needed.
    for (int i = 0; i < numsSize - 1; i++) {
        // 從 index i 最遠能跳到 i + nums[i] / from i we can reach i + nums[i]
        // nums[i] 等同於 *(nums + i)，是指標索引語法 / nums[i] is *(nums + i), pointer indexing
        int reach = i + nums[i];

        // 更新「下一跳能到的最遠處」 / update the farthest reachable in one more jump
        farthest = MAX(farthest, reach);

        // 走到目前這一跳的右邊界，必須再跳一次。
        // We've consumed this jump's range; commit one more jump.
        if (i == currentEnd) {
            jumps++;                  // 跳一次 / make a jump
            currentEnd = farthest;    // 進入下一層的右邊界 / move to next layer's boundary

            // 小優化：若已能涵蓋終點，可提前結束。
            // Optimization: if we can already reach the end, break early.
            if (currentEnd >= numsSize - 1) break;
        }
    }

    return jumps;  // 回傳最少跳躍次數 / return the minimum number of jumps
}