LogoKode$word

LeetCode 1306: Jump Game III – Java DFS & Graph Traversal Solution Explained

Learn how to solve LeetCode 1306 Jump Game III using DFS and graph traversal in Java. Includes brute force intuition, optimized recursive solution, BFS approach, dry run, complexity analysis, interview explanation, and common mistakes.

Krishna Shrivastava
2 views
LinkedInGithubX
0
0
LeetCodeMediumDFSBFSGraph TraversalJavaRecursion
LeetCode 1306: Jump Game III – Java DFS & Graph Traversal Solution Explained
Listen to articleAudio version
Ad
Advertisement

Introduction

LeetCode 1306 – Jump Game III is an interesting graph traversal problem that combines:

  1. Depth First Search (DFS)
  2. Breadth First Search (BFS)
  3. Recursion
  4. Visited tracking
  5. Cycle detection

At first glance, this problem looks like an array problem.

But internally, it behaves exactly like a graph traversal problem where:

  1. Each index acts like a node
  2. Each jump acts like an edge

This problem is commonly asked in coding interviews because it tests:

  1. Recursive thinking
  2. Graph traversal intuition
  3. Avoiding infinite loops
  4. State tracking

Problem Link

🔗 https://leetcode.com/problems/jump-game-iii/

Problem Statement

You are given:

  1. An array arr
  2. A starting index start

From index i, you can jump:

i + arr[i]

or

i - arr[i]

Your goal is to determine whether you can reach any index having value:

0

Example

Input

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

Output

true

Explanation

Possible path:

5 → 4 → 1 → 3

At index:

3

Value becomes:

0

So answer is:

true

Understanding the Problem

Think of every index as a graph node.

From each node:

index i

we have two possible edges:

i + arr[i]

and

i - arr[i]

The goal is simply:

Can we reach any node containing value 0?

Brute Force Intuition

A naive recursive solution would:

  1. Try both forward and backward jumps
  2. Continue recursively
  3. Stop when we find zero

Why Brute Force Fails

Without tracking visited indices, recursion may enter infinite loops.

Example:

1 → 3 → 1 → 3 → 1...

This creates cycles.

So we must track visited nodes.

DFS Intuition

We perform DFS traversal from the starting index.

At every index:

  1. Check boundaries
  2. Check if already visited
  3. Check if value is zero
  4. Explore both possible jumps

Key DFS Observation

Each index should only be visited once.

Why?

Because revisiting creates cycles and unnecessary computation.

So we use:

HashSet<Integer> visited

or

boolean[] visited

Recursive DFS Approach

Steps

1. Boundary Check

If index goes outside array:

return false

2. Visited Check

If already visited:

return false

3. Found Zero

If current index contains:

0

Return:

true

4. Explore Both Directions

Try:

start + arr[start]

and

start - arr[start]

Java DFS Solution

class Solution {

public boolean solve(HashSet<Integer> zeroIndexes,
HashSet<Integer> visited,
int start,
int[] arr) {

if(start >= arr.length || start < 0)
return false;

if(visited.contains(start))
return false;

visited.add(start);

if(zeroIndexes.contains(start))
return true;

return solve(zeroIndexes,
visited,
start + arr[start],
arr)

||

solve(zeroIndexes,
visited,
start - arr[start],
arr);
}

public boolean canReach(int[] arr, int start) {

HashSet<Integer> visited = new HashSet<>();

HashSet<Integer> zeroIndexes = new HashSet<>();

for(int i = 0; i < arr.length; i++) {

if(arr[i] == 0) {
zeroIndexes.add(i);
}
}

return solve(zeroIndexes,
visited,
start,
arr);
}
}

Simpler Optimized DFS Solution

We actually do not need a separate set for zero indexes.

We can directly check:

arr[start] == 0

Cleaner Java DFS Solution

class Solution {

public boolean dfs(int[] arr,
boolean[] visited,
int start) {

if(start < 0 || start >= arr.length)
return false;

if(visited[start])
return false;

if(arr[start] == 0)
return true;

visited[start] = true;

return dfs(arr,
visited,
start + arr[start])

||

dfs(arr,
visited,
start - arr[start]);
}

public boolean canReach(int[] arr, int start) {

return dfs(arr,
new boolean[arr.length],
start);
}
}

Dry Run

Input

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

Step 1

Current index:

5

Value:

1

Possible jumps:

5 + 1 = 6
5 - 1 = 4

Step 2

Visit index:

4

Value:

3

Possible jumps:

4 + 3 = 7 (invalid)
4 - 3 = 1

Step 3

Visit index:

1

Value:

2

Possible jumps:

1 + 2 = 3
1 - 2 = -1 (invalid)

Step 4

Visit index:

3

Value:

0

Return:

true

BFS Approach

This problem can also be solved using BFS.

Instead of recursion:

  1. Use queue
  2. Explore neighbors level by level

Java BFS Solution

class Solution {

public boolean canReach(int[] arr, int start) {

Queue<Integer> queue = new LinkedList<>();

boolean[] visited = new boolean[arr.length];

queue.offer(start);

while(!queue.isEmpty()) {

int index = queue.poll();

if(index < 0 || index >= arr.length)
continue;

if(visited[index])
continue;

if(arr[index] == 0)
return true;

visited[index] = true;

queue.offer(index + arr[index]);

queue.offer(index - arr[index]);
}

return false;
}
}

Time Complexity Analysis

DFS Complexity

Time Complexity

O(N)

Each index is visited at most once.

Space Complexity

O(N)

Due to recursion stack and visited array.

BFS Complexity

Time Complexity

O(N)

Space Complexity

O(N)

DFS vs BFS

ApproachAdvantagesDisadvantages
DFSSimple recursive logicRecursion stack
BFSIterative solutionQueue management

Interview Explanation

In interviews, explain:

This problem behaves like graph traversal where each index acts as a node and jumps act as edges. We use DFS or BFS with visited tracking to avoid infinite cycles.

This demonstrates strong graph intuition.

Common Mistakes

1. Forgetting Visited Tracking

This causes infinite recursion.

2. Missing Boundary Checks

Always check:

start < 0 || start >= arr.length

3. Revisiting Nodes

Avoid processing already visited indices.

FAQs

Q1. Is this an array problem or graph problem?

Internally it is a graph traversal problem.

Q2. Which is better: DFS or BFS?

Both are valid.

DFS is usually simpler for this problem.

Q3. Why do we need visited tracking?

To avoid infinite loops caused by cycles.

Q4. Can this be solved greedily?

No.

Because multiple paths must be explored.

Conclusion

LeetCode 1306 is an excellent beginner-friendly graph traversal problem.

It teaches:

  1. DFS traversal
  2. BFS traversal
  3. Cycle detection
  4. Recursive thinking
  5. Visited state management

The most important insight is:

Treat every index as a graph node.

Once you understand this idea, many graph and traversal interview problems become much easier.

Related Articles

Find Length of Loop in Linked List — Complete Guide with Intuition, Dry Run & Floyd’s Cycle Algorithm

Find Length of Loop in Linked List — Complete Guide with Intuition, Dry Run & Floyd’s Cycle Algorithm

Detect Loop and Calculate Its Length Efficiently Using Fast & Slow Pointer Technique

Read Article
LeetCode 39: Combination Sum – Java Backtracking Solution with Dry Run & Complexity

LeetCode 39: Combination Sum – Java Backtracking Solution with Dry Run & Complexity

Master LeetCode 39 Combination Sum using Backtracking in Java with easy explanation, recursion tree, intuition, dry run, complexity analysis, and optimized coding approach.

Read Article
Fast and Slow Pointer Technique in Linked List: Cycle Detection, Proof, and Complete Explanation

Fast and Slow Pointer Technique in Linked List: Cycle Detection, Proof, and Complete Explanation

Why Fast Moves 2 Steps? Why They Meet? How Cycle Start Is Found? — Everything Explained Simply + Deeply

Read Article
LeetCode 102: Binary Tree Level Order Traversal – Java BFS Solution Explained

LeetCode 102: Binary Tree Level Order Traversal – Java BFS Solution Explained

Learn how to solve LeetCode 102 Binary Tree Level Order Traversal using BFS and Queue in Java. Includes brute force intuition, optimized level order traversal, dry run, complexity analysis, interview explanation, and common mistakes.

Read Article
Ai Assistant Kas