Circular Array Loop

#132 Most AskedMedium

Circular Array Loop #132 Most Asked

Medium

4 views

Topics:

Arrays

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?

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the array contain negative numbers, zeros, or non-integer values?
What constitutes a 'loop'? Specifically, does a loop of length 1 (a single element pointing to itself) qualify as a valid loop?
If no loop exists, what should I return (e.g., null, false, an empty array)?
Are all elements in the array guaranteed to be within the bounds of the array size, or could there be an index out of bounds situation if we follow the chain?
Does the 'loop' have to involve all elements of the array, or can it be a subset?

Brute Force Solution

Approach

The problem asks if, starting from some point in a circle, you can follow a path based on given instructions and return to the starting point. The brute force approach is like trying every possible path from every starting point to see if any path forms a cycle.

Here's how the algorithm would work step-by-step:

Pick a starting position in the circle.
Follow the instruction at that position to move to a new position.
From the new position, follow its instruction to move again.
Keep moving and following instructions.
If you ever arrive back at your starting position, check if you've made a valid loop (meaning you've moved at least once). If so, you've found a solution. If you stayed put, it's not a valid loop.
If you move off the edge of the circle at any point, this path doesn't work, so abandon it.
If you've taken more steps than there are positions in the circle without finding a cycle, then abandon this path because it is too long.
Repeat this process, starting from every other position in the circle, until you either find a valid loop or you've tried every possible starting position.

Code Implementation

def circular_array_loop_brute_force(numbers):
    array_length = len(numbers)

    for start_index in range(array_length):
        current_index = start_index
        path_length = 0
        visited_indices = []

        while path_length <= array_length:
            next_index = (current_index + numbers[current_index]) % array_length

            # Check for zero-length loop
            if next_index == current_index:
                break

            # Rule out mixed direction loops
            if numbers[current_index] * numbers[next_index] < 0:
                break

            # Check if we've returned to the start
            if next_index == start_index:
                if path_length + 1 >= 1:
                    return True
                else:
                    break

            # Check if index has been visited
            if next_index in visited_indices:
                break

            visited_indices.append(next_index)
            current_index = next_index
            path_length += 1

    return False

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through each of the n starting positions in the array. For each starting position, it attempts to traverse a path following the instructions in the array. In the worst case, for each starting position, the path might visit up to n positions before either returning to the starting position, going out of bounds, or exceeding n steps. Thus, the nested loops result in roughly n * n operations, leading to a time complexity of O(n²).

Space Complexity

O(1) – The algorithm outlined in the plain English explanation primarily involves iterating through the array and moving between indices. It doesn't mention the creation of any auxiliary data structures like temporary arrays, lists, or hash maps. Only a few variables are needed to keep track of the current and starting positions during path traversal. Therefore, the auxiliary space used remains constant regardless of the input array size, N.

Optimal Solution

Approach

We want to figure out if a series of hops within a circle will eventually lead us back to where we started. The efficient way to do this is to keep track of where we've been and quickly identify when we're going around in circles, but not the good kind.

Here's how the algorithm would work step-by-step:

Imagine each number as a direction and a distance to jump. Start at any position within our circle.
Follow the direction and distance indicated by the number in the current position to get to the next position.
Mark the places we've visited as we move. Think of leaving a temporary tag on each location.
Before moving to the next position, check if we're trying to move in a direction opposite of the direction we have previously been going. If so, this path does not lead to a cycle, and we can ignore it.
If we ever land on a location we've already tagged on the current path, and we're moving in the same direction, that means we've found a valid cycle. We're going in circles!
If, while moving, we go outside the boundaries of our circle, this path will not lead to a cycle, and we can ignore it.
Repeat these steps starting from each position in the circle until we find a cycle or have explored every possible path.

Code Implementation

def circular_array_loop(nums):    array_length = len(nums)
    for start_index in range(array_length):
        current_index = start_index
        path_history = set()
        direction = nums[start_index] > 0
        while True:
            next_index = (current_index + nums[current_index]) % array_length
            # If index is out of bounds.
            if next_index < 0:
                next_index += array_length
            
            # Check for opposite direction.
            if (nums[next_index] > 0) != direction:
                break
            
            # Cycle detection. Mark the current index as visited.
            if next_index in path_history:
                # Ensure cycle has length > 1
                if next_index == current_index:
                    break
                return True

            path_history.add(current_index)
            current_index = next_index

            # Detect if path has exceeded length
            if len(path_history) > array_length:
                break
    return False

Big(O) Analysis

Time Complexity

O(n) – The outer loop iterates through each of the n elements in the input array. Inside this loop, we traverse the array following the jumps. Each element is visited at most once during the cycle detection because we mark visited elements. If we encounter a previously marked element during the current path, or a change in direction, we terminate that path. Therefore, in the worst case, each element in the array will be visited as part of one path, leading to O(n) time complexity.

Space Complexity

O(N) – The algorithm marks visited locations during each path traversal. This is achieved by tagging each location with a temporary value to indicate it's been visited in the current path. In the worst-case scenario, we might traverse all N locations of the array before detecting a cycle or reaching an invalid path. Thus, we potentially modify the input array in-place to track visited nodes for each starting position. While we are modifying the input array which might lead some to think this is O(1) space, because it's stated that we are tagging the location and treating the input array as immutable, we must assume that we are creating a copy of the input array to store these tags. Hence the space complexity is O(N).

Edge Cases

Case	How to Handle
Null or empty input array	Return false immediately as no loop can exist.
Array of size 1	Return false since a single element cannot form a loop.
All elements are zero	Return false as all movements are stationary, preventing a loop.
Array contains only positive numbers that sum to less than the array length	Return false because the loop can never reach all elements to circle back.
Array contains only negative numbers that sum to greater than negative the array length	Return false because the loop can never reach all elements to circle back.
Array contains a mix of positive and negative numbers that prevent a loop.	The algorithm should still correctly identify that the paths do not result in a loop, and terminate.
Integer overflow when calculating the next index.	Use modulo operator (%) to ensure the index remains within the array bounds, preventing overflow.
Different direction movements in a single potential loop.	Mark elements visited in the wrong direction as invalid to prevent cycles using opposite signs.

Null or empty input array

How to Handle:

Return false immediately as no loop can exist.

Array of size 1

How to Handle:

Return false since a single element cannot form a loop.

All elements are zero

How to Handle:

Return false as all movements are stationary, preventing a loop.

Array contains only positive numbers that sum to less than the array length

How to Handle:

Return false because the loop can never reach all elements to circle back.

Array contains only negative numbers that sum to greater than negative the array length

How to Handle:

Return false because the loop can never reach all elements to circle back.

Array contains a mix of positive and negative numbers that prevent a loop.

How to Handle:

The algorithm should still correctly identify that the paths do not result in a loop, and terminate.

Integer overflow when calculating the next index.

How to Handle:

Use modulo operator (%) to ensure the index remains within the array bounds, preventing overflow.

Different direction movements in a single potential loop.

How to Handle:

Mark elements visited in the wrong direction as invalid to prevent cycles using opposite signs.