Find a Same-Direction Cycle in a Circular Array
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
### Find a Same-Direction Cycle in a Circular Array
You are given a circular array `nums` of nonzero integers. From index `i`, move forward by `nums[i]` positions when it is positive, or backward by `abs(nums[i])` positions when it is negative. Movement wraps around either end of the array.
Determine whether these movements contain a valid cycle. A valid cycle must:
- Repeat a sequence of **more than one distinct index** indefinitely.
- Use values that are either all positive or all negative at the cycle's indices.
A cycle that mixes forward and backward jumps is invalid. A jump that returns directly to its own index is also invalid, even if it travels around the array before returning.
Return `true` if at least one valid cycle exists; otherwise return `false`.
### Function Interface
```cpp
class Solution {
public:
bool circularArrayLoop(vector<int>& nums);
};
```
### Examples
**Example 1**
```text
Input: nums = [1,1,3,1]
Output: true
```
Index `1` moves forward to `2`. Index `2` moves forward three positions, wrapping to `1`. The cycle `1 -> 2 -> 1` has two distinct indices and only positive jumps.
**Example 2**
```text
Input: nums = [1,-1,3]
Output: false
```
Indices `0` and `1` lead to each other, but their jumps have opposite signs. Index `2` jumps back to itself after one complete turn. Neither cycle is valid.
### Constraints
- `1 <= nums.size() <= 5000`.
- `-1000 <= nums[i] <= 1000`.
- `nums[i] != 0` for every input element.
### Clarifications
- The sign requirement applies to the indices in the repeating cycle. An unrelated index with the opposite sign does not invalidate a cycle elsewhere.
- The cycle length counts distinct visited indices, not the number of array positions crossed by a jump.
- A negative jump must wrap correctly, including when it crosses index `0`.
### What a Strong Answer Covers
- A precise check of the direction and cycle-length requirements.
- Correct behavior for wraparound, single-index loops, and cycles in different parts of the array.
- A proof of the result and an honest time and auxiliary-space analysis.
### Follow-up Questions
- Can you achieve `O(n)` time and `O(1)` extra space?
Overview: Check a circular jump array for a cycle with more than one index and a consistent direction, including wraparound and one-index loop cases.
