Circular Array Loop in Java
A circular array comprised of positive and negative integers, a cycle in this context is a repeating sequence of movements. If you discover a positive integer k at position i, go forward k steps; if it's a negative integer -k, go back k steps. The array's circular form means that the last element connects to the first and vice versa.
To qualify as a cycle, the following conditions must be met:
1. The cycle must start and end with the same index.
2. The length of the cycle must be greater than 1.
3. All movements in the cycle must be consistent in one direction, either forward or backward.
Example 1:
Input: [2, -1, 1, 1]
Output: true, Cycle detected
Explanation: There is a cycle from index 0 -> 2 -> 3 -> 0.
Example 2:
Input: [-1, 2, 3]
Output: false, No cycle found
Explanation: There is no cycle. The movement from index 0 -> 1 -> 2 is not a cycle, as the cycle's length must be greater than 1.
Approach: Using Hash Set
Step 1: Initialize the array by iterating through each entry.
Step 2: If the current element is part of a cycle or has already been visited (nums[i] == 0), proceed to the next element.
Step 3: Use a HashSet (visited) to keep track of visited indices when traversing. Move across the array, changing the current index according to the movement rules. Continue until a cycle (repeated index) is identified or the movement direction shifts.
Step 4: If a cycle is discovered and the visited set is larger than one, return true. If no cycles are discovered after inspecting all elements, return false.
FileName: CircularArrayLoop.java
import java.util.HashSet;
import java.util.Set;
public class CircularArrayLoop {
public static void main(String[] args) {
int[] arr = {2,-1,1,1};
boolean result = circularArrayLoop(arr);
System.out.println(result + ", " + (result ? "Cycle detected" : "No cycle found"));
}
public static boolean circularArrayLoop(int[] nums) {
int n = nums.length;
for (int i = 0; i < n; i++) {
if (nums[i] == 0) {
continue; // Skip elements already visited or part of a cycle
}
Set<Integer> visited = new HashSet<>();
int current = i;
while (nums[current] * nums[i] > 0 && !visited.contains(current)) {
visited.add(current);
current = (current + nums[current] + n) % n; // Calculate the next index, handle negative indices
}
if (visited.size() > 1 && visited.contains(current)) {
return true;
}
}
return false;
}
}
Output:
true, Cycle detected
Complexity Analysis: The code has a time complexity of O(n) and a space complexity of O(n) due to its use of HashSet.
Approach: Using Two Pointers
Step 1: Iterate through each index, simulating movement in the circular array.
Step 2: Use two pointers (slow and fast) to detect cycles during movement.
Step 3: Skip visited elements or those parts of a cycle, marking to avoid infinite loops.
Step 4: Return true if a cycle of length greater than 1 is found.
Step 5: Otherwise, return false indicating no cycle in the array.
FileName: CircularArrayLoop1.java
public class CircularArrayLoop1 {
public static void main(String[] args) {
int[] arr = {2, -1, 1, 1};
boolean result = circularArrayLoop(arr);
System.out.println(result + ", " + (result ? "Cycle detected" : "No cycle found"));
}
public static boolean circularArrayLoop(int[] nums) {
int n = nums.length;
for (int i = 0; i < n; i++) {
if (nums[i] == 0) {
continue; // Skip elements already visited or part of a cycle
}
int slow = i, fast = i;
boolean forward = nums[i] > 0;
do {
slow = getNextIndex(slow, nums, forward);
fast = getNextIndex(fast, nums, forward);
if (fast != -1) {
fast = getNextIndex(fast, nums, forward);
}
} while (slow != -1 && fast != -1 && slow != fast);
if (slow != -1 && slow == fast) {
return true;
}
}
return false;
}
private static int getNextIndex(int currentIndex, int[] nums, boolean forward) {
int nextIndex = (currentIndex + nums[currentIndex]) % nums.length;
if (nextIndex < 0) {
nextIndex += nums.length; // Handle negative indices
}
if (nextIndex == currentIndex || nums[nextIndex] * nums[currentIndex] <= 0) {
nums[currentIndex] = 0; // Mark visited elements to avoid infinite loops
return -1; // Indicates the end of the cycle or invalid movement
}
if (forward != nums[currentIndex] > 0) {
return -1; // Movement direction changed, not part of a valid cycle
}
return nextIndex;
}
}
Output:
true, Cycle detected
Complexity Analysis: The time complexity of the code is O(n), and the space complexity is O(1).