Quick Overview

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.

Find smallest start index avoiding left exit

Company: Uber

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: easy

Interview Round: Onsite

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.

Quick Answer: 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). From index `i`, your next position is `i + jump[i]`. A positive value moves right, a negative value moves left, and `0` keeps you on the same index.\n\nStarting from an index `s`, repeatedly apply this rule:\n- If the next index becomes `< 0`, you have exited through the left boundary.\n- If the next index becomes `>= n`, you have exited on the right and the process stops.\n- The process may also loop forever inside the array.\n\nReturn the smallest starting index `s` such that the process starting from `s` never exits through the left boundary. Exiting on the right or looping inside the array is allowed. If no such starting index exists, return `-1`.

Constraints

  • 0 <= n <= 200000
  • -10^9 <= jump[i] <= 10^9
  • An O(n) solution is expected.

Examples

Input: ([-1, -1, -1, -1, 2],)

Expected Output: 4

Explanation: Indices 0 through 3 eventually move to -1. Starting at 4 jumps to 6, which exits on the right, so the answer is 4.

Input: ([0, -2, 1],)

Expected Output: 0

Explanation: Index 0 jumps to itself forever, which is allowed. Therefore the smallest valid start is 0.

Hints

  1. Think of each index as a node with exactly one outgoing edge to `i + jump[i]`.
  2. If a walk revisits a node already seen in the same exploration, you found an internal cycle, which is safe because it can never suddenly exit left.

Loading coding console...