{x}
blog image

Circular Array Loop

You are playing a game involving a circular array of non-zero integers nums. Each nums[i] denotes the number of indices forward/backward you must move if you are located at index i:

  • If nums[i] is positive, move nums[i] steps forward, and
  • If nums[i] is negative, move nums[i] steps backward.

Since the array is circular, you may assume that moving forward from the last element puts you on the first element, and moving backwards from the first element puts you on the last element.

A cycle in the array consists of a sequence of indices seq of length k where:

  • Following the movement rules above results in the repeating index sequence seq[0] -> seq[1] -> ... -> seq[k - 1] -> seq[0] -> ...
  • Every nums[seq[j]] is either all positive or all negative.
  • k > 1

Return true if there is a cycle in nums, or false otherwise.

 

Example 1:

Input: nums = [2,-1,1,2,2]
Output: true
Explanation: The graph shows how the indices are connected. White nodes are jumping forward, while red is jumping backward.
We can see the cycle 0 --> 2 --> 3 --> 0 --> ..., and all of its nodes are white (jumping in the same direction).

Example 2:

Input: nums = [-1,-2,-3,-4,-5,6]
Output: false
Explanation: The graph shows how the indices are connected. White nodes are jumping forward, while red is jumping backward.
The only cycle is of size 1, so we return false.

Example 3:

Input: nums = [1,-1,5,1,4]
Output: true
Explanation: The graph shows how the indices are connected. White nodes are jumping forward, while red is jumping backward.
We can see the cycle 0 --> 1 --> 0 --> ..., and while it is of size > 1, it has a node jumping forward and a node jumping backward, so it is not a cycle.
We can see the cycle 3 --> 4 --> 3 --> ..., and all of its nodes are white (jumping in the same direction).

 

Constraints:

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

 

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

Solution Explanation for Circular Array Loop

This problem asks to determine if a circular array contains a cycle where all elements in the cycle move in the same direction (all positive or all negative). We can solve this efficiently using a fast and slow pointer approach, similar to cycle detection in linked lists, combined with a marking strategy to avoid revisiting processed nodes.

Approach:

  1. next(i) function: This helper function calculates the next index based on the current index i and the value nums[i]. It handles the circular nature of the array using the modulo operator (%) and ensures that the result is always within the array bounds.

  2. Iteration and Cycle Detection: The main loop iterates through each index i of the nums array.

    • If nums[i] is 0, it means the node has already been processed; we skip it.
    • Otherwise, we initialize slow and fast pointers to i and next(i), respectively.
    • The while loop continues as long as:
      • nums[slow] and nums[fast] have the same sign (both positive or both negative). This ensures we're only following a path of consistent direction.
      • nums[slow] and nums[next(fast)] have the same sign. This condition prevents getting stuck in a single-element loop, which is not considered a valid cycle.
    • Cycle Found: If slow and fast meet (slow == fast) and they are not pointing to the same element as their next step (slow != next(slow)), it means a cycle of length greater than 1 has been found. We immediately return true.
    • Mark Visited Nodes: After checking for a cycle, we mark all nodes in the current path as visited by setting their values to 0. This prevents revisiting them and improves efficiency.

  3. Return False: If the loop completes without finding any cycle, it means no such cycle exists, and we return false.

Time Complexity: O(N), where N is the length of the array. Each node is visited at most a constant number of times (once in the main loop and at most a few times during cycle detection and marking).

Space Complexity: O(1). We use only a constant amount of extra space for variables like slow, fast, n, etc. No additional data structures are used.

Code Explanation (Python):

The Python code directly implements the approach described above. The next(i) function calculates the next index, considering the circularity and direction of movement. The main loop iterates through the array, detects cycles using the fast and slow pointers, and marks visited nodes to avoid redundant processing.

Code Explanation (Other Languages):

The Java, C++, and Go code follow the same logic as the Python code, with minor syntactical differences to accommodate the respective language features. The core algorithm remains consistent across all implementations. The use of % (modulo operator) and careful handling of potential integer overflows are important aspects that are handled correctly in all codes to ensure accurate results.