Cycle and Order

What is this?

Each problem here exploits a relationship between an array's values and its indices. When values are drawn from the index range, following i → nums[i] is a linked list. When the array is a permutation, the running maximum tells you where a sorted block can end. And when you want to count pairs across an ordering, the merge step of a merge sort already visits exactly the right pairs.

💡 Fun fact: Max Chunks To Make Sorted has a one-line solution with a one-sentence proof. On a permutation of 0 … n−1, a chunk can end at index i exactly when max(arr[0..i]) == i — because that means the first i+1 positions hold precisely the values 0 … i, so sorting them internally puts every one where it belongs and nothing needs to cross the boundary. Count those positions and you have the answer. The whole problem is max and a comparison, and it takes longer to justify than to write.

🔓 The 3 problems in this chapter are free. Sign in with Google or Microsoft to start solving.

The one-line idea: ask what the indices tell you about the values, or the values about the indices. All three of these are invisible until you look at the array as a structure rather than as a list.

1. The array as a linked list

slow = fast = nums[0]
while True:
    slow = nums[slow]; fast = nums[nums[fast]]      # phase 1: find a meeting point
    if slow == fast: break

slow = nums[0]
while slow != fast:                                  # phase 2: find the cycle entrance
    slow = nums[slow]; fast = nums[fast]
return slow

n+1 values drawn from 1 … n guarantee two indices pointing to the same place, so the traversal must cycle — and the cycle's entrance is the value with two arrows into it, which is the duplicate.

Phase 2 is the part worth being able to justify. Once the pointers meet, restarting one at the head and advancing both one step at a time makes them meet exactly at the cycle entrance. The reason is arithmetic: at the meeting point, the distance from the head to the entrance equals the distance from the meeting point to the entrance, modulo the cycle length. Interviewers ask for that argument, not for the code.

The constraints are what point here: O(1) space rules out a set, and "do not modify the array" rules out sorting and index marking. What is left is Floyd.

2. The prefix maximum

mx = chunks = 0
for i, v in enumerate(arr):
    mx = max(mx, v)
    if mx == i: chunks += 1
return chunks

Two variables, no allocation. Note this is the version for a permutation of 0 … n−1; the variant that allows duplicates needs a comparison of prefix maxima against suffix minima instead, which is worth naming as the natural follow-up question.

3. Counting during the merge

Reverse Pairs counts pairs where nums[i] > 2 · nums[j] and i < j. During a merge, both halves are already sorted, so a single two-pointer scan counts every cross-half pair before the merge itself runs:

j = 0
for x in left:
    while j < len(right) and x > 2 * right[j]: j += 1
    count += j                                       # every right[0..j) pairs with x

j never resets between iterations of the outer loop — as x increases, so does the count of right values it dominates — which is what makes the counting linear rather than quadratic. The count must be taken before merging, while the two halves are still separate, and the doubling means overflow is a real consideration in fixed-width languages.

4. A 30-second worked example (the duplicate)

nums = [1, 3, 4, 2, 2] — read as a linked list from index 0:

0 → nums[0]=1 → nums[1]=3 → nums[3]=2 → nums[2]=4 → nums[4]=2 → nums[2]=4 → …

as a picture:      0 → 1 → 3 → 2 → 4
                                ↑    ↓
                                 ────

the cycle is 2 → 4 → 2, and its ENTRANCE is 2
two arrows point at 2: from index 3 and from index 4 — the duplicated value

answer: 2

The duplicate is the entrance precisely because it is the one node with two predecessors — which is exactly what "this value appears twice" means once the array is drawn this way. No counting, no sorting, no extra memory.

5. Where you'll actually meet this

• Data integrity checks. Finding a duplicate in a read-only stream under a memory bound is a genuine production constraint.
• Ranking and recommendation analysis. Inversion and reverse-pair counts measure how far two orderings differ.
• Parallel and distributed sorting. Maximum chunk decomposition is exactly how work is split for independent sorting.
• Cycle detection in general. Floyd's algorithm detects loops in linked structures, state machines and hash chains.
• Database query analysis. Counting out-of-order pairs is how sortedness of an index is estimated.

6. Problems in this chapter

▶ Find the Duplicate Number

Find the repeated value without modifying the array or using extra space. Treat i → nums[i] as a linked list and locate the cycle entrance with Floyd's algorithm.
Pattern: cycle detection on an implicit list. Target: O(n) time, O(1) space.

▶ Reverse Pairs

Count pairs with i < j and nums[i] > 2 · nums[j]. Count cross-half pairs during a merge sort, before merging.
Pattern: counting inside a merge sort. Target: O(n log n) time, O(n) space.

▶ Max Chunks To Make Sorted

Most chunks that can be sorted independently. Count the positions where the prefix maximum equals the index.
Pattern: prefix maximum as a boundary test. Target: O(n) time, O(1) space.

7. Common pitfalls 🚫

• Reaching for a hash set. The constraints exist to rule it out; they are pointing at Floyd.
• Skipping phase 2 of Floyd. The meeting point is not the entrance, and the distinction is the question.
• Advancing the fast pointer once in phase 1 or twice in phase 2. It is two, then one.
• Counting reverse pairs after merging, once the halves are indistinguishable.
• Resetting j on each outer iteration, which makes the count quadratic.
• Overflow on 2 · nums[j] in fixed-width languages.
• Applying the prefix-maximum rule to an array with duplicates, where it does not hold and a different comparison is needed.

8. Key takeaways

1. When values index the array, the array is a graph. Draw it.
2. The cycle entrance is the duplicate, because it is the node with two predecessors.
3. Constraints select the algorithm. O(1) space and read-only leave exactly one option.
4. Merge sort counts for free — the sorted halves make cross-pairs countable in one scan.
5. A prefix maximum equal to its index means the prefix is complete and can be closed.
6. Know the follow-up. Duplicates break the chunk rule, and the fix is prefix max versus suffix min.
7. Why interviewers like it: each has a short solution and a real proof, so they can ask why and get a genuine answer or not.

Order: Find the Duplicate Number → Reverse Pairs → Max Chunks To Make Sorted.