Decoding Cycles in an Array !

CIRCULAR ARRAY LOOP , LEETCODE 457.( EXPLAINED WITH FULL WORKING CODE !)

QUESTION

You are given a circular array nums of positive and negative integers. If a number k at an index is positive, then move forward k steps. Conversely, if it's negative (-k), move backward k steps. Since the array is circular, you may assume that the last element's next element is the first element, and the first element's previous element is the last element.

Determine if there is a loop (or a cycle) in nums. A cycle must start and end at the same index and the cycle's length > 1. Furthermore, movements in a cycle must all follow a single direction. In other words, a cycle must not consist of both forward and backward movements.

Example 1:

Input: [2,-1,1,2,2]
Output: true
Explanation: There is a cycle, from index 0 -> 2 -> 3 -> 0. The cycle's length is 3.

Example 2:

Input: [-1,2]
Output: false
Explanation: The movement from index 1 -> 1 -> 1 ... is not a cycle, because the cycle's length is 1. By definition the cycle's length must be greater than 1.

Example 3:

Input: [-2,1,-1,-2,-2]
Output: false
Explanation: The movement from index 1 -> 2 -> 1 -> ... is not a cycle, because movement from index 1 -> 2 is a forward movement, but movement from index 2 -> 1 is a backward movement. All movements in a cycle must follow a single direction.

Note:

1. -1000 ≤ nums[i] ≤ 1000
2. nums[i] ≠ 0
3. 1 ≤ nums.length ≤ 5000

Follow up:

Could you solve it in O(n) time complexity and O(1) extra space complexity?

ASKED IN

Explanation

So at first , we have to comprehend what are the factors that do not make a cycle in the array.

1. The cycle must start and end at the same index of the array but the cycle length should be > 1.

Now what is cycle length ?

Cycle length is the number of elements present in the cycle.

For eg if the array is [ 2 , 1 , 1 ] , then the cycle consists of elements [ 2 , 1 ] and hence the cycle length is 2 which is a valid cycle.

So the only possible scenario where the cycle length can be 1 is

WHEN

arr[start] % arr.length == 0 ,

where ‘arr’ is the array and start is the start index of the cycle.

Let’s consider an example for this.

Let arr = [ 2 , 6, -1] . Here , if we start from index 1 ( consider 0 based indexing ) , then we end up at index 1 every-time , making our cycle length 1.

So all the indices having arr[index] % arr.length == 0 should be avoided.

2. The cycle should only proceed in one direction i.e either forward or backward.

This is pretty easy to understand.

Logically

if arr[start] < 0 ,then , arr[index] should be < 0 where index denotes all the

indices in the same cycle path from ‘start’ index.

OR

if arr[start] > 0 ,then , arr[index] should be >0 where index denotes all the

indices in the same cycle path from ‘start’ index

So we will write a function to check if a cycle is valid or not like below.

Function to check whether a cycle is valid or not

3. A cycle must start and end at the same index. This condition is obviously not a big headache if we think a bit logically.

Let’s say we start from an index ‘i’ in the array , mark every node as visited ( in a boolean array named visited where visited[index] = true if it is already being visited) and if we again come across a visited node , then there is definitely a cycle with starting point equals to the node which is just being visited again. ( Just make sure the cycle conditions hold valid. i.e case 1 and 2).

But hang on.

When we hit a visited node , how are we sure that this node was visited in the current cycle ? It may also be the case that the node that I just visited again was visited before in a previous cycle traversal which I discarded because the cycle condition was not met. Hence only marking true or false in the visited array won’t be enough. We have to leave a mark of our starting node in every next node that we would visit by making visited[cur_index] = start_index , and if I visit an index where visited[cur_index] is already equals to start index , then I know that I have already visited this index before , and most importantly in my CURRENT cycle. An unvisited index can be set to INFINITY to mark it NOT visited initially. We won’t start our mission to find a cycle from any visited index as start index because that is practically of no use and would increase our time complexity as well .

A small observation : If the array contains only positive or negative elements and all the array elements % arr.length != 0 then , there will always be a cycle.

Now we are using an extra space of O(N) where N is the length of the array by using a visited array. This can be avoided by being a little smart and marking the indices in place (in the array itself).

How?

If we look carefully at the constraints , the maximum value that the array can contain is 1000 and the minimum value is -1000. So when we visit an index if we set the arr[index] to some value outside of this domain , then we will be able to understand that this index has already been visited. But we also need to find the start index from which it was visited. Hence , to mark an index visited

We set,

arr[index] = minDomain -start — 1 (if arr[index < 0 ) ,

or

arr[index] = maxDomain + start + 1. (if arr[index] > 0).

In this way we avoid taking the extra visited array and mark visited in place also leaving the trace of the start position of the current cycle. Along the path of the cycle we leave traces of the start of the current cycle so that when we hit a visited node we are sure that this node was visited from the current cycle itself.

If we visit a node which is already being visited but not a part of the current cycle then we can safely break out, as the path from there is already seen before and we know that does not lead to a valid cycle . Had it lead to a valid cycle we would have already returned ‘true’ by now and would not have been checking for the current cycle.

Full working code.

Time Complexity : O(N)

Space Complexity : O(1)

Please note that in line 27 of the above code , I have made nums[index] = nums[index] % n , where n is the length of the ‘nums’ array. This is done so that the array index does not go out of bounds when there are negative numbers.

Consider this case [- 5 , 1 ].

Here next index would be (0–5+2) % 2 = -1 which is not a valid index.

Check out the problem at this link.

Also checkout my YouTube Channel.