Solution: Circular Array Loop

Let's solve the Circular Array Loop problem using the Fast and Slow Pointers pattern.

We'll cover the following

Statement

We are given a circular arrayA circular array is a type of array, where the last element is followed by the first element, forming a loop or circle. of non-zero integers, nums, where each integer represents the number of steps to be taken either forward or backward from its current index. Positive values indicate forward movement, while negative values imply backward movement. When reaching either end of the array, the traversal wraps around to the opposite end.

The input array may contain a cycle, which is a sequence of indexes characterized by the following:

  • The sequence starts and ends at the same index.
  • The length of the sequence is at least two.
  • The loop must be in a single direction, forward or backward.

Note: A cycle in the array does not have to originate at the beginning. It may begin from any point in the array.

Your task is to determine if nums has a cycle. Return TRUE if there is a cycle. Otherwise return FALSE.

Constraints:

  • 1≤1 \leq nums.length ≤103\leq 10^3
  • −5000≤-5000 \leq nums[i] ≤5000\leq 5000
  • nums[i] !=0!= 0

Solution

So far, you’ve probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which to follow based on considerations such as time complexity and implementation constraints.

Naive approach

The naive approach involves iterating through each element of the input array. In each iteration, we start from the current element and check for cycles in both forward and backward directions. We also keep an additional array to track visited elements. If a cycle is detected during this process, we return TRUE. However, if the direction of the cycle changes at any point, we’ll move to the next iteration. We’ll repeat this until we find the cycle or traverse the complete array.

For each element in the outer loop, there is an inner loop that explores potential cycles, resulting in a time complexity of O(n2)O(n^2). The space complexity is O(n)O(n) because we use extra space to keep track of the visited elements. This makes it an inefficient approach for large input arrays.

Optimized approach using fast and slow pointers

We can use the fast and slow pointers technique, where traversing at different speeds enables efficient cycle detection. Comparing the signs of values during traversal facilitates correct navigation in both forward and backward directions within the array.

For each element of the array, two pointers, initialized at that specific element, traverse the array, with one taking one step at a time and the other advancing by two steps. The position of each pointer for the next step is determined by the value it is currently pointing to. If any movement results in the pointer pointing to a value with a different sign (indicating a change in direction) or pointing to the same index it was previously pointing to (indicating a self-loop), move to the next element of the array. Do the same if the fast pointer has reached the end of the linked list and no cycle is detected. However, if there’s a cycle, both pointers eventually catch up. This is because, in the non-cyclic part, the distance between them increases by one index in each iteration. However, upon entering the cyclic part, the fast pointer rapidly closes the gap on the slow pointer, decreasing the distance by one index in each iteration until they meet.

Let's see the workflow of the algorithm. The algorithm involves iterating through each index of nums. For every index, i, perform the following steps:

  1. Initialize fast and slow pointers to the current index i.

  2. Move the slow pointer, either forward or backward, depending on the current value it is pointing to, nums[i]. For example, if the value is −3, the slow pointer is moved three indexes backward. Similarly, if the value is 2, the slow pointer is moved two indexes forward.

  3. Now, check if a valid cycle can be formed. For this, we have two primary checks:If any of the conditions above fail, move to step 4.

    1. If the index of the new value pointed to by slow is the same as the index of the previous value pointed to by slow, that is, the pointer is forming a self-loop, then the next iteration starts.

    2. Observe the sign of the previous value pointed to by slow and the sign of the new value it points to. If both values have different signs, that is, the pointer is not moving in a single direction, then the next iteration starts.

  4. Move the fast pointer twice in a similar fashion, and after every move, check for the validity of the cycle using the same checks as above. If a valid cycle can’t be formed, move to the next index of nums.

  5. Now, check for the existence of the cycle. If the slow and fast pointers meet at the same index, a cycle is detected. Return TRUE in this case. Otherwise, continue moving the pointers until we determine whether or not a cycle exists.

Note: We only move to the next index if a valid cycle cannot be formed with the current index.

If no cycle is detected for any index, return FALSE.

Here’s the demonstration of the steps above:

Press + to interact
canvasAnimation-image
1 of 16

Let’s look at the code for this solution below:

import java.util.*;
class Solution {
    public static boolean circularArrayLoop(int[] nums) {
        int size = nums.length;
        for (int i = 0; i < size; i++) {
            int slow = i, fast = i;
            boolean forward = nums[i] > 0;
            while (true) {
                slow = nextStep(slow, nums[slow], size);
                if (isNotCycle(nums, forward, slow))
                    break;
                fast = nextStep(fast, nums[fast], size);
                if (isNotCycle(nums, forward, fast))
                    break;
                fast = nextStep(fast, nums[fast], size);
                if (isNotCycle(nums, forward, fast))
                    break;
                if (slow == fast)
                    return true;
            }
        }
        return false;
    }
    
    // A function to calculate the next step
    public static int nextStep(int pointer, int value, int size) {
        int result = (pointer + value) % size;
        if (result < 0)
            result += size;
        return result;
    }
    
    // A function to detect a cycle doesn't exist
    public static boolean isNotCycle(int[] nums, boolean prevDirection, int pointer) {
        boolean currDirection = nums[pointer] >= 0;
        if (prevDirection != currDirection || Math.abs(nums[pointer] % nums.length) == 0) {
            return true;
        }
        return false;
    }
    // Driver code
    public static void main(String[] args) {
        int[][] input = {
                {-2, -3, -9},
                {-5, -4, -3, -2, -1},
                {-1, -2, -3, -4, -5},
                {2, 1, -1, -2},
                {-1, -2, -3, -4, -5, 6},
                {1, 2, -3, 3, 4, 7, 1},
                {2, 2, 2, 7, 2, -1, 2, -1, -1}
        };
        for (int i = 0; i < input.length; i++) {
            System.out.println((i + 1) + ".\tCircular array = " + Arrays.toString(input[i]) + "\n");
            boolean result = circularArrayLoop(input[i]);
            System.out.println("\tFound Loop = " + result);
            System.out.println(new String(new char[100]).replace('\0', '-'));
        }
    }
}
Circular Array Loop

Solution summary

To recap, the solution to this problem can be divided into the following parts:

  1. Move the slow pointer xx steps forward/backward, where xx is the value at the ithi^{th} index of the array.
  2. Move the fast pointer xx steps forward/backward, where xx is the value at ithi^{th} index. Then, move fast pointer yy steps forward/backward, where yy is the value at xthx^{th} index.
  3. Return TRUE when both pointers meet at the same point.
  4. If the direction changes after moving the slow or fast pointer or taking a step, return to the same location, then follow the steps above for the next element of the array.
  5. Return FALSE if we have traversed every element of the array without finding a loop.

Time complexity

The outer loop iterates through each element in the input array, contributing O(n)O(n) to the time complexity. Within this loop, there is a while loop that may iterate up to O(n)O(n) times in the worst case. This is because it advances pointers until a cycle is detected or the end of the array is reached. Therefore, in the worst-case scenario, where the while loop iterates through the entire array to detect a cycle, the total time complexity of this solution becomes O(n2)O(n^2).

Space complexity

We are not using any extra space in this algorithm. Therefore, the space complexity of the provided solution is O(1)O(1).

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.