Daily bit(e) of C++ | Reaching the last element
Daily bit(e) of C++ #303, Common interview problem: Reaching the last element.
Today, we will look at a common C++ interview problem: Reaching the last element.
Given an array of positive integers (zero included), determine whether you can reach the final element. You start at index zero and, in one step, can move at most the value at your current position.
Before you continue reading the solution, I encourage you to try to solve it yourself. Here is a Compiler Explorer link with a couple of test cases: https://compiler-explorer.com/z/1oqfq38nb.
Solution
There are plenty of possible complex solutions; however, this is a straightforward problem.
The crucial realization is that if index j is unreachable from index i, then arr[i] < j-i (and this logic applies to all indices before j).
We do not care about how we reach an index, only that we can. This means we can keep track of the current “reachable distance” and process the array in one pass.
