Circular Array Loop Solution in Java

Explore Solutions in Other Languages

Problem Description

Ah, the Circular Array Loop problem! It’s like trying to find your way out of a roundabout that just keeps going in circles. Imagine you’re in a theme park, and you’ve just discovered that the roller coaster you thought would take you to the exit is actually a never-ending loop. You get on, and instead of a thrilling ride, you find yourself back where you started, questioning your life choices.

In this problem, you’re given an array of integers where each integer represents the number of steps to move forward or backward in the array. Your task is to determine if there exists a loop in the array that doesn’t involve any zeroes. If you can find such a loop, congratulations! You’ve just unlocked the secret to infinite amusement park rides!

Code Solution


class Solution {
  public boolean circularArrayLoop(int[] nums) {
    if (nums.length < 2)
      return false;

    for (int i = 0; i < nums.length; ++i) {
      if (nums[i] == 0)
        continue;
      int slow = i;
      int fast = advance(nums, slow);
      while (nums[i] * nums[fast] > 0 && nums[i] * nums[advance(nums, fast)] > 0) {
        if (slow == fast) {
          if (slow == advance(nums, slow))
            break;
          return true;
        }
        slow = advance(nums, slow);
        fast = advance(nums, advance(nums, fast));
      }

      slow = i;
      final int sign = nums[i];
      while (sign * nums[slow] > 0) {
        final int next = advance(nums, slow);
        nums[slow] = 0;
        slow = next;
      }
    }

    return false;
  }

  private int advance(int[] nums, int i) {
    final int n = nums.length;
    final int val = (i + nums[i]) % n;
    return i + nums[i] >= 0 ? val : n + val;
  }
}

Approach

The approach taken in this solution is akin to a slow and fast runner strategy. We use two pointers: a slow pointer that moves one step at a time and a fast pointer that moves two steps at a time. If they meet, we have a loop! But wait, we also need to ensure that the loop is valid, meaning it should not involve any zeroes. If we find a loop, we return true; otherwise, we mark the visited elements as zero to avoid revisiting them.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(n), where n is the number of elements in the array. Each element is processed at most twice.
Space Complexity	O(1), as we are using a constant amount of space for pointers and variables.

Real-World Example

Think of a group of friends at a party who decide to play a game of musical chairs. They keep moving around the chairs based on the number of steps they take, but if someone ends up back at their original chair without anyone else sitting there, they’ve found themselves in a loop! Just like in our problem, if they can keep moving without hitting a zero (an empty chair), they can keep the game going indefinitely.