Find cycle in array

Question

Given an array of integers where each integer represents a position in the array, determine if there is a cycle present. A cycle occurs when you can start at any index and follow the positions to eventually return to the same index. Your solution should return true if a cycle exists and false otherwise.

Codemia · Accepted Answer

The problem requires us to find if there is a cycle in an array where each element points to another index in the array. This problem exhibits characteristics of a graph traversal, where each index in the array can be seen as a node, and the value at that index represents a directed edge to another node. The most suitable approach here is the **Floyd’s Tortoise and Hare algorithm** (also known as cycle detection in linked lists). This approach uses two pointers moving at different speeds to detect cycles, which is efficient in both time and space. 1. Initialize two pointers, `slow` and `fast`. Set `slow` to the first index (0) and `fast` to the index pointed by the first element of the array. 2. Move `slow` one step at a time (i.e., `slow = arr[slow]`), and `fast` two steps at a time (i.e., `fast = arr[arr[fast]]`). 3. If at any point `slow` equals `fast`, a cycle is detected, and we return `True`. 4. If `fast` or the next index to `fast` goes out of bounds, return `False` since there's no cycle. **Example**: For an array [1, 2, 0], `slow` starts at index 0 (points to 1), and `fast` starts at index 1 (points to 2). In the next iteration, `slow` moves to index 1 (points to 2), and `fast` moves to index 0 (points to 1), and continues this until a cycle is detected or we go out of bounds. Here is the Python implementation of the proposed solution: ```python def hasCycle(arr): if not arr or len(arr) == 1: return False slow = 0 fast = 0 while True: slow = arr[slow] fast = arr[arr[fast]] if slow == fast: return True if fast < 0 or fast >= len(arr) or arr[fast] < 0 or arr[fast] >= len(arr): return False ``` This code checks for cycles using the aforementioned two-pointer technique. The time complexity of this solution is O(n) because each pointer traverses the array at most once. The space complexity is O(1) as we are using only a fixed amount of extra space (for the pointers). This efficiency makes it suitable for large input sizes, as it does not require additional data structures. 1. **Empty Input**: An empty array should return `False` as there are no indices to form a cycle. 2. **Single Element**: An array with one element pointing to itself (e.g., [0]) should return `True` as it forms a cycle. 3. **Negative Indices**: If the array contains indices that are negative or out of bounds (e.g., [1, -1, 2]), the solution should handle this gracefully and return `False`. 4. **Multiple Elements without Cycle**: An array like [1, 2, 0] should return `False` if it does not form a cycle.

Find cycle in array

Rippling

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Problem Analysis

Approach

Submit Your Answer

Rippling Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string