What is the brute force approach and complexity for Jump Game III?

Recursively try both jumps from each index, and stop any walk after n jumps with time complexity O(2^N) and space complexity O(N).

What is the optimal approach and complexity for Jump Game III?

Visit each reachable index once, in any order, and check each one for a 0 with optimal time complexity O(N) and space complexity O(N).

How do you identify the pattern for Jump Game III?

Look for key signals in the prompt: "jump to i + arr[i] or i − arr[i]" indicates Both directions are allowed, so each index has two neighbours. The jumps form a graph, not a line.; "reach any index with value 0" indicates We need only one target, so a search that finds every reachable index is enough.; "cannot jump outside the array" indicates A neighbour outside the array is just a missing arrow..

Jump Game III

Medium·LeetCode #1306 Pro OnlyPattern Transfer

LeetCode

Problem Statement

You get an array arr of non-negative integers and a starting index start. From index i you can jump forward to i + arr[i] or backward to i − arr[i]. You can never jump outside the array.

Return true if you can reach any index whose value is 0, and false otherwise.

Input

An array arr and a starting index start.

Output

true if an index holding 0 can be reached from start, otherwise false.

Example 1

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

Output: true

Jump back from index 5 to index 4 (5 − 1), back to index 1 (4 − 3), then forward to index 3 (1 + 2). Index 3 holds 0.

Example 2

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

Output: true

Jump forward from index 0 to index 4 (0 + 4), back to index 1 (4 − 3), then forward to index 3 (1 + 2).

Example 3

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

Output: false

From index 2 you can reach only indexes 0, 2, 3 and 4. None of them holds 0. Index 1, which holds 0, is never reached.

Constraints

• 1 ≤ arr.length ≤ 5 · 10^4
• 0 ≤ arr[i] < arr.length
• 0 ≤ start < arr.length

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“jump to i + arr[i] or i − arr[i]”

→ Both directions are allowed, so each index has two neighbours. The jumps form a graph, not a line.

“reach any index with value 0”

→ We need only one target, so a search that finds every reachable index is enough.

“cannot jump outside the array”

→ A neighbour outside the array is just a missing arrow.

Approach Complexity Ladder

Brute Force — try both jumps, no memoryO(2^N)O(N)

Recursively try both jumps from each index, and stop any walk after n jumps

Optimal — BFS with a visited setO(N)O(N)

Visit each reachable index once, in any order, and check each one for a 0

Brute Force Intuition

From index i, try jumping to i + arr[i] and to i − arr[i], recursing on each one that stays inside the array. If an index holds 0, return true. There is no visited set, so an index can be entered again and again. To stop endless back-and-forth, cut a walk off after n jumps.

Recognition rule for this sub-pattern:

Track the farthest point you can reach so far; the answer depends only on that frontier.

Remember this · Greedy

Trigger

Maximise count / minimise cost with a natural "best next step", sorting makes the choice obvious, reachability.

Think

Is there a choice I can always make safely without looking ahead?

Key question

Why can't the greedy choice be worse than the optimal one? (Try to break it with a small example.)

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Greedy translate into production architectures and low-level memory mechanics.

LLD Architecture