LeetCode 457: Circular Array Loop Solution

Master LeetCode problem 457 (Circular Array Loop), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

457. Circular Array Loop

Medium

Array Hash Table Two Pointers

Problem Explanation

Explanation:

To solve this problem, we can use the concept of Floyd's Tortoise and Hare algorithm, also known as cycle detection algorithm. We will iterate through each index of the array and try to find cycles by moving two pointers at different speeds. If there is a cycle in the array, the two pointers will eventually meet at some index.

Algorithm:

Iterate through each index of the array.
For each index, start two pointers - slow and fast.
Move the slow pointer one step forward/backward based on the value at the current index.
Move the fast pointer two steps forward/backward based on the value at the current index.
If the array has a cycle, the slow and fast pointers will eventually meet at the same index.
Check if the cycle length is greater than 1 and if all elements in the cycle have the same sign.
If both conditions are met, return true.

Time Complexity:

The time complexity of this solution is O(n), where n is the number of elements in the array.

Space Complexity:

The space complexity of this solution is O(1) as we are using constant extra space.

Solution Code

class Solution {
    public boolean circularArrayLoop(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            if (hasCycle(nums, i)) {
                return true;
            }
        }
        return false;
    }

    private boolean hasCycle(int[] nums, int start) {
        int slow = start, fast = start;
        int n = nums.length;

        boolean isForward = nums[start] > 0;

        do {
            slow = getNextIndex(nums, slow, isForward);
            fast = getNextIndex(nums, fast, isForward);
            if (fast != -1) {
                fast = getNextIndex(nums, fast, isForward);
            }
        } while (fast != -1 && slow != -1 && slow != fast);

        if (slow != -1 && slow == fast) {
            int curr = slow;
            int cycleLength = 0;
            boolean sameDirection = nums[slow] > 0;
            do {
                curr = getNextIndex(nums, curr, isForward);
                cycleLength++;
            } while (curr != slow);

            return cycleLength > 1 && sameDirection;
        }

        return false;
    }

    private int getNextIndex(int[] nums, int i, boolean isForward) {
        int n = nums.length;
        int next = (i + nums[i] % n + n) % n;
        if (next == i || nums[next] == 0 || (nums[next] > 0) != isForward) {
            return -1;
        }
        return next;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 457 (Circular Array Loop)?

This page provides optimized solutions for LeetCode problem 457 (Circular Array Loop) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 457 (Circular Array Loop)?

The time complexity for LeetCode 457 (Circular Array Loop) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 457 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 457 in Java, C++, or Python.

Back to LeetCode Solutions