Find Length of Loop — Editorial

Opening the reading…

Intuitionthe values do not matter; the next-index rule does

The array describes links between positions, not comparisons between values. Position i points to position i + 1 until the last position; when x is positive, the last position points back to position x - 1 because x is 1-based. The values stored in those positions can repeat freely, so they never help determine the loop length.

This gives you a linked-list traversal using only integer indices. A slow pointer advances one link at a time and a fast pointer advances two. If the structure is cyclic, the fast pointer eventually catches the slow pointer inside the cycle. Once they meet, keep one index fixed and advance the other until it returns; the number of advances is exactly the number of nodes in the cycle.

The array is only a compact way to represent links between positions.

Approachdetect first, then measure the closed walk

Let nextIndex(i) return i + 1 for every non-tail position and x - 1 for the tail, because this reproduces the linked-list pointer without constructing any node objects.

Return 0 immediately when x is 0, because the tail points to null and there is no cycle for the two pointers to discover.

Start slow and fast at index 0, then move slow once and fast twice on every iteration, because different speeds are what force the pointers to meet inside a reachable cycle.

Stop when slow equals fast, because equality means both pointers occupy the same node after following the same deterministic links; with x positive, the cycle guarantees that this eventually happens.

Set length to 1 and move one pointer once from the meeting node, because the meeting node already counts as the first cycle node and the next step begins the lap.

Continue moving that pointer one link and incrementing length until it returns to the fixed meeting node, because the first return completes exactly one traversal of every cycle node.

Return length, which counts the cycle nodes rather than the nodes before the cycle or the number of pointer steps used to detect it.

Complexitythe array is read as a constant-space linked list

MEASURE	BOUND	WHY
Time	O(n)	The detection phase makes a bounded number of link traversals before the faster pointer closes the gap in the cycle, and the counting phase makes one complete cycle traversal. The non-cyclic prefix and cycle together contain at most n positions, so no phase needs more than a constant number of visits per position.
Space	O(1) extra	Only two indices and one counter are stored; nextIndex computes each link directly instead of building nodes or a visited set. This remains constant even in the worst shape, where the tail points to the head and all n positions form the cycle.

Here n is the number of elements in values. The returned integer is output storage and is excluded from auxiliary space.

Annotated solutionC++ · Floyd detection on array indices

CPPMap each pointer move to an array index, detect a meeting, then count one complete cycle.

#include <vector>

using namespace std;

class Solution {
public:
    int lengthOfLoop(vector<int> values, int x) {
        int n = static_cast<int>(values.size());
        if (x == 0) {
            return 0;
        }

        auto nextIndex = [&](int index) {
            return index + 1 == n ? x - 1 : index + 1;
        };

        int slow = 0;
        int fast = 0;

        do {
            slow = nextIndex(slow);
            fast = nextIndex(nextIndex(fast));
        } while (slow != fast);

        int length = 1;
        fast = nextIndex(slow);
        while (fast != slow) {
            fast = nextIndex(fast);
            ++length;
        }

        return length;
    }
};

The nextIndex lambda is the central translation from the problem's array representation to linked-list behavior. Every ordinary index advances by one, while the tail wraps to x - 1. The do-while loop is safe after the x == 0 guard: when x is positive, the structure is guaranteed to contain a cycle, so the pointers should move before the first equality check.