How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at TikTok.

What role is this question designed for?

This question is commonly asked for Machine Learning Engineer candidates at TikTok during technical interviews.

Determine frog reachability across stones

Company: TikTok

Role: Machine Learning Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Onsite

You are given a sorted array of distinct integers stones representing stone positions in a river, where stones[0] = 0. A frog starts on stone 0; its first jump must be 1 unit. If its last jump was k units, the next jump must be k−1, k, or k+1 units (and must be > 0). Determine whether the frog can reach the last stone. Design and justify an efficient algorithm (e.g., DP with hash sets or maps), including correctness arguments and time/space complexity. Follow-ups: discuss pruning strategies and worst-case inputs.

Quick Answer: This question evaluates dynamic programming, state-space reachability, and constrained transition reasoning, along with skills in hash-based memoization and time/space complexity analysis.

You are given a sorted array of distinct integers `stones` representing stone positions in a river, where `stones[0] == 0`. A frog starts on stone 0; its first jump must be exactly 1 unit. If the frog's last jump was `k` units, its next jump must be `k - 1`, `k`, or `k + 1` units, and must be strictly greater than 0. The frog can only land on a position that contains a stone. Return `true` if the frog can reach the last stone (the position `stones[-1]`), and `false` otherwise. Use dynamic programming: track, for each reachable stone, the set of jump sizes that can land on it. From each such state, try jumps of size `k-1`, `k`, `k+1`. This runs in O(n^2) time and O(n^2) space in the worst case.

Constraints

2 <= stones.length <= 2000 (single-stone and empty inputs are handled defensively)
0 <= stones[i] <= 2^31 - 1
stones[0] == 0
stones is sorted in strictly increasing order (distinct values)
The first jump must be exactly 1 unit; if it cannot be made, the answer is false unless the array has a single stone.

Examples

Input: ([0,1,3,5,6,8,12,17],)

Expected Output: True

Explanation: Jumps of 1,2,2,3,4,5 (with allowed adjustments) reach 17: 0->1->3->5->8->12->17. The frog can reach the last stone.

Input: ([0,1,2,3,4,8,9,11],)

Expected Output: False

Explanation: There is a gap of 4 units between stone 4 and stone 8; arriving at 4 with at most jump size 1 cannot bridge to 8, so the last stone is unreachable.

Input: ([0,1],)

Expected Output: True

Explanation: The mandatory first jump of size 1 lands directly on the last stone at position 1.

Input: ([0],)

Expected Output: True

Explanation: The frog already stands on the only/last stone, so no jump is needed.

Input: ([0,2],)

Expected Output: False

Explanation: The first jump must be exactly 1 unit, which lands on water at position 1; the frog can never reach position 2.

Input: ([0,1,3,6,10,13,14],)

Expected Output: True

Explanation: 0->1 (k=1), 1->3 (k=2), 3->6 (k=3), 6->10 (k=4), then 10->14 (k=4) lands directly on the last stone.

Input: ([0,1,2,3,4,5,6,7],)

Expected Output: True

Explanation: Consecutive stones one unit apart: the frog can keep jumping size 1 (k-1=... still allowed since k stays >=1) straight to the last stone.

Hints

If stones[1] != 1, the frog can never make its mandatory first jump of size 1, so the answer is immediately false (for arrays with more than one stone).
For each stone, remember the SET of jump sizes that can land on it, not just whether it is reachable. The same stone reached by different jump sizes leads to different future moves.
From a stone reached with jump size k, the next jump can be k-1, k, or k+1 (each must be > 0). Add the new jump size to the target stone's set only if that target position is an actual stone.
You can short-circuit and return true as soon as any jump lands exactly on the last stone's position.
Use a hash set of stone positions for O(1) membership tests; a position not in the set is water and cannot be landed on.

Quick Overview

This question evaluates dynamic programming, state-space reachability, and constrained transition reasoning, along with skills in hash-based memoization and time/space complexity analysis.