What is the brute force approach and complexity for Circular Array Loop?

From each index, take n same-direction jumps; check the loop you are in with time complexity O(N²) and space complexity O(1).

What is the optimal approach and complexity for Circular Array Loop?

Floyd with direction/self-loop checks; set failed paths to 0 so each index is walked once with optimal time complexity O(N) and space complexity O(1).

Circular Array Loop

Q: How do you identify the pattern for Circular Array Loop?

Look for key signals in the prompt: "jump nums[i] steps from i" indicates Each index has exactly one next index → a hidden linked list.; "circular array" indicates Next index wraps around with modulo — careful with negatives in C++.; "is there a cycle" indicates Cycle detection → Floyd's slow/fast pointers.; "same direction, length > 1" indicates Extra validity rules: some moves are not allowed..

Medium·LeetCode #457 Pro OnlyPattern Transfer

LeetCode

Problem Statement

You are given a circular array nums of non-zero integers. Standing at index i, you jump nums[i] places: forward if it is positive, backward if it is negative. Because the array is circular, going past the last index wraps to the start, and going before index 0 wraps to the end.

Return true if the array contains a valid cycle: a sequence of jumps that comes back to where it started, where

every index in the cycle has the same sign (all jumps forward, or all jumps backward), and
the cycle has more than one index (an index that jumps onto itself does not count).

Otherwise return false.

Input

An integer array nums with no zeros.

Output

true if a valid cycle exists, otherwise false.

Example 1

Input: nums = [2, -1, 1, 2, 2]

Output: true

0 → 2 → 3 → 0. All three jumps are forward and the cycle has 3 indices.

Example 2

Input: nums = [-1, -2, -3, -4, -5, 6]

Output: false

Index 5 jumps 6 places and lands on itself — a cycle of length 1, which does not count. Every other path ends up mixing backward and forward jumps.

Example 3

Input: nums = [1, -1, 5, 1, 4]

Output: true

0 → 1 → 0 mixes directions, so it is not valid. But 3 → 4 → 3 (jump 1, then jump 4 which wraps) is all forward with length 2.

Constraints

• 1 ≤ nums.length ≤ 5000
• −1000 ≤ nums[i] ≤ 1000
• nums[i] ≠ 0
• Follow-up: can you solve it in O(N) time and O(1) extra space?

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“jump nums[i] steps from i”

→ Each index has exactly one next index → a hidden linked list.

“circular array”

→ Next index wraps around with modulo — careful with negatives in C++.

“is there a cycle”

→ Cycle detection → Floyd's slow/fast pointers.

“same direction, length > 1”

→ Extra validity rules: some moves are not allowed.

Approach Complexity Ladder

Brute Force — simulate n jumps from every startO(N²)O(1)

From each index, take n same-direction jumps; check the loop you are in

Optimal — Floyd per start + clear dead pathsO(N)O(1)

Floyd with direction/self-loop checks; set failed paths to 0 so each index is walked once

Brute Force Intuition

For every start, keep jumping. If any jump lands on an index with the other sign, this start fails. If we survive n jumps, we must already be inside the loop this walk ends in (a path can't visit more than n different indices). Then the loop is valid unless it is a single index jumping onto itself, which we check with one more next.

Recognition rule for this sub-pattern:

Fast moves 2, slow moves 1. If there is a loop, fast catches slow. Reset one to head to find the loop start.

Remember this · Linked List — Fast & Slow

Trigger

Cycle detection, middle of list, "n-th from end", two lists meeting, repeating sequences.

Think

If one pointer moves faster or starts earlier, where will they meet?

Key question

What speed or gap makes the meeting point tell me the answer?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Linked List — Fast & Slow translate into production architectures and low-level memory mechanics.

LLD Architecture