Count cycle in array

Question

Given an array of integers, count the number of distinct cycles present in the array. A cycle is defined as a sequence of indices where the value at each index points to the next index in the cycle, and the last index points back to the first index in the cycle. Your function should return the total count of such cycles found in the array.

Codemia · Accepted Answer

To solve the problem of counting distinct cycles in an array, we can utilize a **depth-first search (DFS)** approach. The reason this pattern applies is that each index points to another index, forming a graph structure where we can traverse through the indices to find cycles. A cycle is characterized by visiting an index that we've already seen during our traversal, indicating we've returned to a starting point. This method efficiently identifies all unique cycles without double-counting them.

1. **Initialization**: Begin by initializing a set to keep track of visited indices and a counter for cycles. 
2. **Traversal**: Loop through each index of the array. For each index that hasn't been visited, follow the indices it points to until you either revisit a visited index or reach an index that points outside the array bounds. 
3. **Cycle Detection**: During the traversal, if you revisit an index that is part of the current traversal path, you have detected a cycle. Increment the cycle counter. 
4. **Marking Visited**: Mark each index as visited once it is processed to avoid redundant checks. 
5. **Continue**: Repeat for all indices and return the cycle count.

**Example**: For an array `[1, 2, 0, 4, 3]`, the traversal starts at index 0: 
- 0 -> 1 -> 2 -> 0 forms a cycle. 
- 3 -> 4 -> 3 forms another cycle. Thus, the output should be 2.

Here is the Python implementation of the above approach:

```python
def count_cycles(arr):
    visited = set()
    cycle_count = 0

for i in range(len(arr)):
        if i not in visited:
            current = i
            current_path = set()

while current < len(arr) and current not in visited:
                if current in current_path:
                    cycle_count += 1
                    break
                current_path.add(current)
                visited.add(current)
                current = arr[current]

return cycle_count
```
This function checks each index, traverses the array using the values at the indices, and counts distinct cycles.

The time complexity of this solution is O(n), where n is the length of the input array. This is because each index is processed at most twice: once when we start a traversal and once when we mark it as visited. The space complexity is also O(n) due to the storage required for the `visited` set and the `current_path` set used during traversal. Given the constraints of the problem, this is efficient and optimal.

1. **Empty Array**: If the input array is empty, the function should return 0, as there are no cycles.
2. **Single Element**: An array with a single element pointing to itself, e.g., `[0]`, should return 1, as it forms a cycle. 
3. **No Cycles**: An array where indices point outside of their bounds, e.g., `[1, 2, 3, 4]` (if the array has length 4), should return 0. 
4. **Multiple Disjoint Cycles**: Arrays like `[1, 0, 3, 4, 2]` should be handled correctly, returning the accurate count of disjoint cycles.

Count cycle in array

NVIDIA

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

NVIDIA 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