algoadvance

Leetcode 457. Circular Array Loop

Problem Statement

Given an array of integers nums, you need to determine if there is a loop in nums. The loop must be a cyclic sequence in which the sum of the elements (the entries within the loop) is strictly greater than zero, and it must be whole. Each element in the array can be used only once. Additionally, you need to ensure the following:

  1. The loop indices are allowed to cycle forward or backward.
  2. A loop must be made of at least two elements.

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

Clarifying Questions

  1. Can the loop span in both positive and negative directions?
    • Yes, loops can move forward or backward depending on the values in nums.
  2. Can the loop use just one element repeating itself?
    • No, the loop must consist of at least two distinct elements.
  3. Can we assume all input values are valid integers?
    • Yes, the input array nums consists of integers.
  4. What is the range of elements in the nums array and its length?
    • The length of the array nums could be very large, up to 10^4. Each element in the array can be within the range of smallest negative integer to the largest positive integer within typical C++ integer bounds.

Strategy

  1. Loop Detection Using Two Pointers (Tortoise and Hare Algorithm):
    • Use two pointers (slow and fast) to detect cycles.
    • The slow pointer moves one step at a time, while the fast pointer moves two steps at a time.
  2. Direction Consistency:
    • Ensure that all elements in the loop move in a consistent direction.
    • If the loop starts moving forward, all elements in the loop should move forward and vice versa.
  3. Visited Tracking:
    • Use an auxiliary space to track visited elements to prevent reprocessing.
  4. Edge Cases:
    • Single element arrays or arrays with all elements as 0 should directly return false.

Code

#include <vector>

using namespace std;

class Solution {
public:
    bool circularArrayLoop(vector<int>& nums) {
        int n = nums.size();
        
        auto next_index = [&](int index) {
            return ((index + nums[index]) % n + n) % n;
        };
        
        for (int i = 0; i < n; ++i) {
            if (nums[i] == 0) continue;
            
            int slow = i, fast = i;
            bool is_forward = nums[i] > 0;
            
            while (true) {
                slow = next_index(slow);
                if (is_forward != (nums[slow] > 0) || nums[slow] == 0) break;
                
                fast = next_index(fast);
                if (is_forward != (nums[fast] > 0) || nums[fast] == 0) break;
                fast = next_index(fast);
                if (is_forward != (nums[fast] > 0) || nums[fast] == 0) break;
                
                if (slow == fast) {
                    if (slow == next_index(slow)) break; // Single-element loop
                    return true;
                }
            }
            
            slow = i;
            int val = nums[i];
            while (nums[slow] != 0) {
                int next = next_index(slow);
                nums[slow] = 0;
                slow = next;
            }
        }
        
        return false;
    }
};

Time Complexity

The time complexity is O(n) since each element is visited at most twice:

  1. Once in the outer loop.
  2. Once more when marking all elements in the confirmed non-cyclic path as 0 to avoid reprocessing.

The space complexity is O(1) as we are using only a few extra variables regardless of the input size.

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