Jump Game III - Practice Coding Problems

Jump Game III - Problem

Given an array of non-negative integers arr, you are initially positioned at start index of the array. When you are at index i, you can jump to i + arr[i] or i - arr[i].

Check if you can reach any index with value 0.

Notice that you cannot jump outside of the array at any time.

Input & Output

Example 1 — Basic Reachable Case

$ Input: arr = [4,2,3,0,3,1,2], start = 5

› Output: true

💡 Note: Start at index 5 (value 1). Can jump to index 6 (5+1) or index 4 (5-1). From index 4 (value 3), can jump to index 1 (4-3) or index 7 (out of bounds). From index 1, can reach index 3 which has value 0.

Example 2 — Unreachable Zero

$ Input: arr = [4,2,3,0,3,1,2], start = 0

› Output: true

💡 Note: Start at index 0 (value 4). Can jump to index 4 (0+4). From index 4 (value 3), can reach index 1 or 7. From index 1, can reach index 3 which has value 0.

Example 3 — No Zero Reachable

$ Input: arr = [3,0,2,1,2], start = 2

› Output: false

💡 Note: Start at index 2 (value 2). Can jump to index 0 (2-2) or index 4 (2+2). From these positions, cannot reach index 1 which contains the only zero.

Constraints

1 ≤ arr.length ≤ 5 × 10⁴
0 ≤ arr[i] < arr.length
0 ≤ start < arr.length

Visualization

Tap to expand

Understanding the Visualization

Input Array

Array with jump distances and starting position

Jump Rules

From index i, can jump to i+arr[i] or i-arr[i]

Goal

Find if any position with value 0 is reachable

Key Takeaway

🎯 Key Insight: Transform array jumping into graph traversal with cycle detection

Asked in

f Facebook 25 A Amazon 18 G Google 15 M Microsoft 12

The key insight is to treat this as a graph traversal problem where each index can connect to at most two other indices. Use DFS or BFS with visited tracking to avoid cycles while exploring all reachable positions. Best approach is DFS with visited set: Time O(n), Space O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Breadth-First Search	O(n)	O(n)	Use BFS with a queue to explore positions level by level
Recursive DFS without Memoization	O(2^n)	O(n)	Try all possible jumps recursively without tracking visited positions
Depth-First Search with Visited Set	O(n)	O(n)	Use DFS with a visited set to avoid cycles and redundant exploration

Breadth-First Search — Algorithm Steps

Initialize queue with start position and visited set
While queue is not empty, dequeue current position
Check if current position has value 0
Add valid unvisited neighbors to queue
Return true if zero found, false if queue empty

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Add start position to queue and mark as visited

Process Queue

Dequeue position and add valid neighbors to queue

Find Zero

Return true immediately when zero value is found

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>

bool solution(int* arr, int arrSize, int start) {
    if (arr[start] == 0) return true;
    
    int queue[1000];
    bool visited[1000] = {false};
    int front = 0, rear = 0;
    
    queue[rear++] = start;
    visited[start] = true;
    
    while (front < rear) {
        int pos = queue[front++];
        
        int nextPositions[2] = {pos + arr[pos], pos - arr[pos]};
        for (int i = 0; i < 2; i++) {
            int nextPos = nextPositions[i];
            if (nextPos >= 0 && nextPos < arrSize && !visited[nextPos]) {
                if (arr[nextPos] == 0) return true;
                visited[nextPos] = true;
                queue[rear++] = nextPos;
            }
        }
    }
    
    return false;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    int arr[100];
    int arrSize = 0;
    char* token = strtok(line, "[],\n");
    while (token != NULL) {
        if (strlen(token) > 0) {
            arr[arrSize++] = atoi(token);
        }
        token = strtok(NULL, "[],\n");
    }
    int start;
    scanf("%d", &start);
    bool result = solution(arr, arrSize, start);
    printf(result ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Each position is visited at most once, exploring all n positions in worst case

✓ Linear Growth

Space Complexity

O(n)

Queue and visited set can each contain up to n positions

⚡ Linearithmic Space

76.4K Views

Medium Frequency

~15 min Avg. Time

1.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Breadth-First Search — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler