algoadvance

Leetcode 457. Circular Array Loop

Problem Statement

You are given a circular array nums of positive and negative integers. If a number k at an index is positive, move forward k steps. Conversely, if it’s negative, move backward k steps. Since the array is circular, you may assume that the last element’s next element is the first element and the first element’s previous element is the last element.

Determine if there is a loop in this array. A loop starts and ends at a particular index with more than 1 element along the loop. The loop must be entirely in a single direction (forward or backward).

Return true if there is a loop in the array, otherwise, return false.

Clarifying Questions

  1. Can the loop contain only positive numbers or only negative numbers?
    • Yes, but the direction should be consistent (i.e., all positive or all negative).
  2. What should we return if the loop consists of a single element?
    • The loop must consist of more than 1 element.
  3. Are we allowed to modify the input array?
    • No explicit restriction, but ideally, the solution should be optimal without altering the input if necessary.

Strategy

  1. Traversal and Loop Detection Using Two Pointers:
    • Use the tortoise and hare approach to detect cycles.
    • Iterate through each index as a starting point.
    • Use two pointers to detect cycle, keeping track of direction.
  2. Direction Check:
    • Ensure that all elements in the detected cycle have the same sign.
  3. Visited Marking:
    • Mark already visited elements to avoid redundant calculations.

Code

public class Solution {
    public boolean circularArrayLoop(int[] nums) {
        int n = nums.length;
        
        // Function to get the next index in a circular manner.
        int nextIndex(int[] nums, int currentIndex) {
            int n = nums.length;
            int next = (currentIndex + nums[currentIndex]) % n;
            if (next < 0) next += n;
            return next;
        }
        
        for (int i = 0; i < n; i++) {
            if (nums[i] == 0) continue; // Already visited or part of a 0-length loop.
            
            // Start exploration from index i.
            int slow = i, fast = i;
            boolean isForward = nums[i] > 0; // Direction.

            // Explore until we find a loop or confirm no loop exists.
            while (true) {
                slow = nextIndex(nums, slow);
                fast = nextIndex(nums, fast);
                if (isForward != (nums[fast] > 0)) break;
                fast = nextIndex(nums, fast);
                if (isForward != (nums[fast] > 0)) break;

                if (slow == fast) {
                    if (slow == nextIndex(nums, slow)) {
                        break; // Single-element loop.
                    }
                    return true; // Valid loop found.
                }
            }

            // Mark visited elements in the current direction.
            slow = i;
            while (nums[slow] != 0) {
                int temp = slow;
                slow = nextIndex(nums, slow);
                nums[temp] = 0;
            }
        }
        
        return false;
    }
}

Time Complexity

This algorithm combines cycle detection using the Floyd’s Tortoise and Hare approach with direction and visited checking. It efficiently handles the complexity of circular and directional array navigation.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI