Jump Game - JS Solution

Editorial

Editorial solutions and visualizations are prepared with care, but we do not guarantee 100% accuracy or completeness. Please use your own judgment to verify results. Visucodize is not responsible for decisions made based on this content.

const REACHABLE_RANGE = 'reachable_range', REACHABLE_RANGE_COLOR = 'gold';
const CURRENT_INDEX = 'current_index', CURRENT_INDEX_COLOR = 'blue';

function visMainFunction(inputNums) {
    initClassProperties();
    explanationAndColorSchemaNotifications();

    startBatch();
    const nums = VisArray.from(inputNums).options({ label: 'Jump Array' });
    const lastIndex = nums.length - 1;

    let farthestReachable = 0;
    makeVisVariable(farthestReachable).options({ label: 'farthestReachable' }).createVis();
    highlightReachableIndices(nums, -1, farthestReachable);

    let currentIndex = 0;
    makeVisVariable(currentIndex).registerAsIndexPointer(nums, CURRENT_INDEX);
    endBatch();

    notification(`
        ▶️ <b>Initial setup</b>
        <ul>
            <li><b>${makeColoredSpan('currentIndex', CURRENT_INDEX_COLOR)}</b> starts at <b>0</b> — it represents the position currently being evaluated in the jump array.</li>
            <li><b>${makeColoredSpan('farthestReachable', REACHABLE_RANGE_COLOR)}</b> also starts at <b>0</b> — it marks the furthest index that can currently be reached (initially just the start).</li>
            <li><b>lastIndex</b> is the final target position (<code>nums.length - 1</code>) — reaching or exceeding it means success.</li>
            <li>We will iterate forward, checking whether <b>${makeColoredSpan('currentIndex', CURRENT_INDEX_COLOR)}</b> is still within the reachable range, and extending <b>${makeColoredSpan('farthestReachable', REACHABLE_RANGE_COLOR)}</b> whenever a farther index becomes reachable.</li>
            <li>The process continues until we either reach or exceed <b>lastIndex</b> (success) or encounter a gap where <b>${makeColoredSpan('currentIndex', CURRENT_INDEX_COLOR)} > ${makeColoredSpan('farthestReachable', REACHABLE_RANGE_COLOR)}</b> (failure).</li>
        </ul>
    `);

    while (currentIndex <= lastIndex) {
        startPartialBatch();

        if (currentIndex > farthestReachable) {
            notification(`
              ❌ <b>Failed at index ${currentIndex}</b>
              <ul>
                <li>Current index <b>${currentIndex}</b> is beyond <b>farthestReachable = ${farthestReachable}</b>.</li>
                <li>No previously reachable position can jump here → reachability is broken (a gap exists).</li>
                <li><b>Conclusion:</b> It’s impossible to reach the last index.</li>
              </ul>
            `);
            return false;
        }

        const jumpLength = nums[currentIndex];
        const newReach = currentIndex + jumpLength;

        notification(`
          📌 <b>At index ${currentIndex}</b>
          <ul>
            <li>Jump length = <b>${jumpLength}</b> → can reach up to <b>${newReach}</b> from here.</li>
            <li>Current <b>farthestReachable</b> = <b>${farthestReachable}</b>.</li>
          </ul>
        `);

        if (newReach > farthestReachable) {
            notification(`
              🔄 <b>Extending reach</b>
              <ul>
                <li>New maximum reach found: <b>${newReach}</b> &gt; <b>${farthestReachable}</b>.</li>
                <li>Update <b>farthestReachable</b>: <b>${farthestReachable}</b> → <b>${newReach}</b>.</li>
                <li>The newly reachable indices are highlighted with ${makeColoredSpan(REACHABLE_RANGE_COLOR + ' background', REACHABLE_RANGE_COLOR)}.</li>
              </ul>
            `);
            highlightReachableIndices(nums, farthestReachable, newReach);
            farthestReachable = newReach;
        } else {
            notification(`
              ↔️ <b>No extension</b>
              <ul>
                <li>Reach from here: <b>${newReach}</b> ≤ current <b>farthestReachable = ${farthestReachable}</b>.</li>
                <li>Keep <b>farthestReachable</b> unchanged.</li>
              </ul>
            `);
        }

        if (farthestReachable >= lastIndex) {
            notification(`
              ✅ <b>Success</b>
              <ul>
                <li><b>farthestReachable = ${farthestReachable}</b> ≥ <b>lastIndex = ${lastIndex}</b>.</li>
                <li>The continuous reachable segment already covers the goal.</li>
                <li>We can reach the last index.</li>
              </ul>
            `);
            return true;
        }

        currentIndex += 1;
        endBatch();
    }
}

function explanationAndColorSchemaNotifications() {
    explanationNotification();
    notification(`
        🎨 <b>Color Legend</b>
        <ul>
            <li><b>${makeColoredSpan('currentIndex', CURRENT_INDEX_COLOR)}</b> — the position currently being evaluated in the array.</li>
            <li><b>${makeColoredSpan('farthestReachable', REACHABLE_RANGE_COLOR)}</b> — marks all indices that are currently reachable (the continuous frontier of progress).</li>
        </ul>
    `);
}

function highlightReachableIndices(arr, prevMaxReachable, newMaxReachable) {
    startBatch();
    for (let index = prevMaxReachable + 1; index <= newMaxReachable; index++) {
        arr.makeVisManagerForIndex(index).addClass(REACHABLE_RANGE);
    }
    endBatch();
}

function initClassProperties() {
    setClassProperties(REACHABLE_RANGE, { backgroundColor: REACHABLE_RANGE_COLOR });
    setClassProperties(CURRENT_INDEX, { borderColor: CURRENT_INDEX_COLOR });
}

Approach

The algorithm determines whether we can reach the last index in the array using a greedy reachability check. We maintain a single variable, farthestReachable, representing the furthest index that can currently be reached.

We iterate through the array from left to right.
- If the currentIndex is greater than farthestReachable, it means no earlier position can reach currentIndex, creating a gap in reachability. Since every future position depends on a previous reachable one, we must immediately stop and return false.
- Otherwise, currentIndex lies within the reachable range. We compute how far we can jump from here using newReach = currentIndex + nums[currentIndex], and update: farthestReachable = max(farthestReachable, newReach)
- If at any point farthestReachable ≥ lastIndex, it means the reachable segment already covers the target, so we can safely return true.

🧠 Key Intuition

Continuous reachability: From any index j, you may choose any jump distance between 0 and nums[j]. If a farther index k is reachable from j, then all intermediate indices between j and k are also reachable by taking shorter jumps.
Inductive linkage: Every reachable index k > 0 is reached from some earlier reachable index j < k. Combining this with the contiguous-range property above, we conclude that reachability expands outward as a continuous prefix — meaning if k is reachable, all indices in [0, k] are reachable (0 is included since it is the starting point).
At iteration currentIndex:
- If currentIndex ≤ farthestReachable, it lies within the current continuous reachable segment — meaning it can be reached from some earlier index or is the start itself.
- If currentIndex > farthestReachable, it cannot be reached from any previous reachable index, nor can it be the start, so it is unreachable. Since every future step relies on a reachable predecessor, the process must terminate with false.

📈 Flow Summary

Initialize farthestReachable = 0.
For each index currentIndex:
- If currentIndex > farthestReachable → return false.
- Compute newReach = currentIndex + nums[currentIndex] and update farthestReachable as max(farthestReachable, newReach).
- If farthestReachable ≥ lastIndex → return true.

Time Complexity

The algorithm makes a single pass through the array, updating farthestReachable at each step using constant-time operations. Therefore, the total running time is O(n).

Space Complexity

The algorithm maintains only a few scalar variables — currentIndex, farthestReachable, and lastIndex — without any additional data structures. Thus, the space complexity is O(1).

Input-1

Input-2

Jump Game - JS Solution

Solution code

Solution explanation

Solution explanation

Approach

🧠 Key Intuition

📈 Flow Summary

Time Complexity

Space Complexity