Every Loop in a Circular Jump Array
Updated
Problem statement
You are given a circular array nums of n non-zero integers. Standing at index i, you jump |nums[i]| steps: forward (toward higher indices) if nums[i] is positive, and backward if it is negative. Because the array is circular, a jump past the last index continues from index 0, and a jump before index 0 continues from the last index. In other words, from index i you land on index (i + nums[i]) mod n, taken in the range 0 to n - 1.
A loop is a group of indices that you keep visiting: start at one of them and keep jumping, and you come back to it after visiting each other index of the group exactly once. The jumps inside a loop may go in either direction.
Return every loop. Write each loop as the list of its indices in the order you visit them, starting from its smallest index. Order the loops by their first index.
Function
findAllLoops(nums: int[]) → List<List<Integer>>Examples
Example 1
nums = [2,-1,-1,2,2,-2,5]return = [[0,2,1],[3,5],[4,6]]From index 0 the jumps go 0 → 2 → 1 → 0 (+2, then -1, then -1), so [0, 2, 1] is a loop even though its jumps go both ways. 3 → 5 → 3 gives [3, 5]. 4 → 6 → 4 gives [4, 6]: from index 6 the jump of 5 wraps around, because 6 + 5 = 11 and 11 - 7 = 4. Every index is on one of these three loops.
Example 2
nums = [1,1,1,-2,4]return = [[1,2,3]]The walk from 0 goes 0 → 1 → 2 → 3 → 1: index 3 jumps back 2 steps to index 1. So indices 1, 2 and 3 form a loop. Index 0 leads into it but is never reached again. Index 4 jumps 4 steps: 4 + 4 = 8, which wraps to 8 - 5 = 3, also into the loop. The only loop is [1, 2, 3].
Example 3
nums = [-1,1]return = [[0,1]]Index 0 jumps one step back and wraps to index 1. Index 1 jumps one step forward and wraps to index 0. So the two indices form the loop [0, 1].
Constraints
2 <= nums.length <= 10^4nums[i] != 0-(nums.length - 1) <= nums[i] <= nums.length - 1
More Nutanix Online Assessment questions
- Good SubsequencesOA · Seen Jul 2026
- Min Cost to Connect All PointsOA · Seen Jun 2026
- Digit Changes for a Multiple of 9OA · Seen Aug 2025
- Gas Station Loop StartOA · Seen Aug 2025
- Number of Players (for MTS2)OA · Seen Oct 2024
- Work Schedules (for MTS2)OA · Seen Oct 2024
- Minimum Operations to Convert ArrayOA · Seen Apr 2024
- No Adjacent CharactersOA · Seen Apr 2024
- Build a BST From a ListOA · Seen Nov 2022
- Delete Even-Valued Nodes From a Linked ListOA · Seen Nov 2022
Similar questions at other companies
- Maximum Damage PatchGecko Robotics · OA · PHONE SCREEN
- Directed Path ExistenceUnity · OA
- Delete and Compact a Forest SubtreePinterest · PHONE SCREEN · ONSITE INTERVIEWPinterest interview questions
- Number of Islands with Diagonal ConnectivityGoogle · ONSITE INTERVIEWGoogle interview questions
- Island Count and Maximum AreaOracle · ONSITE INTERVIEWOracle interview questions
- Deterministic Depth-First Graph TraversalWaymo · PHONE SCREENWaymo interview questions
- Count Islands in a Binary GridApple · PHONE SCREENApple interview questions
- Query Whether an Island Size ExistsMeta · ONSITE INTERVIEWMeta interview questions
- Pacific Atlantic Water FlowAnduril · PHONE SCREENAnduril interview questions
- Detonate Bombs with Chain ReactionsAirbnb · PHONE SCREENAirbnb interview questions