Determine frog reachability across stones

Q: Determine frog reachability across stones

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

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

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.

Determine frog reachability across stones

Overview

Comments (0)