Solution: Problem Challenge 3: Cycle in a Circular Array

Grokking the Coding Interview: Patterns for Coding Questions

Ask Author

Back to course home

0% completed

Vote For New Content

Solution: Problem Challenge 3: Cycle in a Circular Array

Table of Contents

Contents are not accessible

Problem Statement

We are given an array containing positive and negative numbers. Suppose the array contains a number ‘M’ at a particular index. Now, if ‘M’ is positive we will move forward ‘M’ indices and if ‘M’ is negative move backwards ‘M’ indices. You should assume that the array is circular which means two things:

If, while moving forward, we reach the end of the array, we will jump to the first element to continue the movement.
If, while moving backward, we reach the beginning of the array, we will jump to the last element to continue the movement.

Write a method to determine if the array has a cycle. The cycle should have more than one element and should follow one direction which means the cycle should not contain both forward and backward movements.

Example 1:

Input: [1, 2, -1, 2, 2]
Output: true
Explanation: The array has a cycle among indices: 0 -> 1 -> 3 -> 0

Example 2:

Input: [2, 2, -1, 2]
Output: true
Explanation: The array has a cycle among indices: 1 -> 3 -> 1

Example 3:

Input: [2, 1, -1, -2]
Output: false
Explanation: The array does not have any cycle.

Constraints:

1 <= nums.length <= 5000
`-1000 <= nums[i] <= 1000
nums[i] != 0

Solution

This problem involves finding a cycle in the array and, as we know, the Fast & Slow pointer method is an efficient way to do that. We can start from each index of the array to find the cycle. If a number does not have a cycle we will move forward to the next element. There are a couple of additional things we need to take care of:

As mentioned in the problem, the cycle should have more than one element. This means that when we move a pointer forward, if the pointer points to the same element after the move, we have a one-element cycle. Therefore, we can finish our cycle search for the current element.
The other requirement mentioned in the problem is that the cycle should not contain both forward and backward movements. We will handle this by remembering the direction of each element while searching for the cycle. If the number is positive, the direction will be forward and if the number is negative, the direction will be backward. So whenever we move a pointer forward, if there is a change in the direction, we will finish our cycle search right there for the current element.

Here is the visual representation of this algorithm for Example-1:

Code

Here is what our algorithm will look like:

Python3

. . . .

Time Complexity

The above algorithm will have a time complexity of $O(N^2)$ where ‘N’ is the number of elements in the array. This complexity is due to the fact that we are iterating all elements of the array and trying to find a cycle for each element.

Space Complexity

The algorithm runs in constant space O(1).

An Alternate Approach

In our algorithm, we don’t keep a record of all the numbers that have been evaluated for cycles. We know that all such numbers will not produce a cycle for any other instance as well. If we can remember all the numbers that have been visited, our algorithm will improve to $O(N)$ as, then, each number will be evaluated for cycles only once. We can keep track of this by creating a separate array, however, in this case, the space complexity of our algorithm will increase to $O(N)$ .

Step-by-Step Algorithm

Initialize Visited Array:
- Create a boolean array visited to keep track of visited indices, initially set to false.
Iterate Through Each Index:
- Loop through each index i in the array arr.
- If i is already visited, skip to the next index.
- Determine the direction of movement (isForward) based on the sign of arr[i].
Initialize Slow and Fast Pointers:
- Set both slow and fast pointers to the current index i.
Cycle Detection Using Slow and Fast Pointers:
- Enter a loop to move the slow and fast pointers.
  - Move Slow Pointer:
    - Move slow one step using the findNextIndex function.
  - Move Fast Pointer:
    - Move fast one step using the findNextIndex function.
    - If fast is not -1, move fast another step using the findNextIndex function.
  - Continue this loop until slow and fast pointers meet or one of them becomes -1.
Check for Cycle:
- If slow and fast pointers meet (and neither is -1), a cycle is detected.
- Return true indicating a cycle is found.
Mark Visited Indices:
- If no cycle is found, mark all indices visited during this cycle detection attempt:
  - Initialize index to startIndex.
  - While index is not -1 and not already visited:
    - Mark visited[index] as true.
    - Move index to the next index using the findNextIndex function.
Return Result:
- If no cycle is detected for any index, return false.

Thank you for the correction. Here is the revised walkthrough for the array [2, 2, -1, 2] with the proper explanation of each step:

Algorithm Walkthrough

Let's consider the input: arr = [2, 2, -1, 2].

Initial Setup:
- Input array: [2, 2, -1, 2]
- Initialize visited array: [False, False, False, False]
Index 0:
- Not visited, continue.
- isForward is True (since arr[0] is 2).
- slow = 0, fast = 0.
First Loop:
- Move Slow Pointer:
  - slow = findNextIndex([2, 2, -1, 2], True, 0) = 2
- Move Fast Pointer:
  - fast = findNextIndex([2, 2, -1, 2], True, 0) = 2
  - fast = findNextIndex([2, 2, -1, 2], True, 2) = -1 (direction change)
- The loop terminates as fast becomes -1.
Mark Visited Indices:
- Mark all indices visited in this cycle detection attempt starting from index 0:
  - visited = [True, False, True, False]
Index 1:
- Not visited, continue.
- isForward is True (since arr[1] is 2).
- slow = 1, fast = 1.
First Loop:
- Move Slow Pointer:
  - slow = findNextIndex([2, 2, -1, 2], True, 1) = 3
- Move Fast Pointer:
  - fast = findNextIndex([2, 2, -1, 2], True, 1) = 3
  - fast = findNextIndex([2, 2, -1, 2], True, 3) = 1
- slow is 3, fast is 1. Continue loop.
Second Loop:
- Move Slow Pointer:
  - slow = findNextIndex([2, 2, -1, 2], True, 3) = 1
- Move Fast Pointer:
  - fast = findNextIndex([2, 2, -1, 2], True, 1) = 3
  - fast = findNextIndex([2, 2, -1, 2], True, 3) = 1
- slow is 1, fast is 1. They meet, cycle detected.
- So, return true.

The cycle in arr is 1 -> 3 -> 1.

Code

Python3

. . . .

Complexity Analysis

Time Complexity: $O(N)$
- Outer Loop: The outer loop runs through each index in the array. Each index is visited at most once due to the visited array, ensuring that each element is processed only once.
- Inner Loop (Cycle Detection): The inner loop, which uses the slow and fast pointers to detect a cycle, runs in constant time for each element because we are using a do-while loop and breaking out as soon as a cycle is detected or the pointers meet a -1.

Each element is processed a constant number of times, making the overall time complexity $O(N)$ .

Space Complexity: $O(N)$
- Visited Array: The additional visited array used to track which indices have been visited has a size equal to the input array, resulting in an $O(N)$ space complexity.

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible