Katkat
Back

Find smallest start index avoiding left exit

UberSoftware Engineer · Onsite
EasySoftware EngineerOnsiteCoding & Algorithms

Last updated

This question evaluates a candidate's ability to analyze reachability and cycle behavior in array-based functional graphs, testing competency in array manipulation, traversal, loop detection, and runtime optimization within the Coding & Algorithms domain.

You are given an integer array jump of length n (0-indexed). If you are currently at index i, your next position becomes i + jump[i] (a positive value moves right, a negative value moves left).

Starting from an index s, you repeatedly apply this move rule.

  • If you ever reach an index < 0, you have moved out of the left boundary.
  • If you reach an index >= n, you have moved out of the array on the right (you may treat this as stopping).
  • The process may also loop inside the array.

Return the smallest starting index s such that, during the entire process starting from s, you never move out of the left boundary (i.e., the sequence of visited indices never becomes negative). If no such index exists, return -1.

Implement an algorithm that runs in O(n) time if possible.