educative.io

Educative

How the input ([2, 1, -1, -2]) given in example 3 has no cycle?

Input: [2, 1, -1, -2]
Adjacency Map :
0 → 2
1 → 2
2 → 1
3 → 1
`
The array has a cycle among indices: 2 → 1 → 2. Please clarify the reason behind evaluating it to false.

Hi @vinod_kumar_ragunath,
The loop between the indices must be a circular loop of complete array., which means it must go beyond the bounds of the array. Because the last member of the array is not included in the loop, the loop does not satisfy the criterion of a circular loop in the given input.

Let’s break it down with some examples.
Example 1:

Input: [1, -1]
As you can see there is loop but it is not fulfilling the condition mentioned above. So the answer is False.

Example 2:

Input: [2, -1, 1]
As you can see there is a loop and it is also fulfilling the condition of circular loop of complete array. . So the answer is True.

Example 3:

Input: [2, -1, 1, -3]
As you can see there is a loop and last element of the array is also included in a loop but the loop did not go beyond the bounds of the array. So its answer is also False.