</> MAANG.io

Advanced

Advanced problems where modelling is the hard part: implicit graphs, tricky DP states, intervals and design challenges.

0 of 95 solved 0%

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.

Cycle and Order: three problems where values relate to indices

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. 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 code is max and a comparison, and the proof 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 thread through all three: ask what the indices tell you about the values, or the values about the indices. Each one is 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. 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 (O(n log n), and it mutates) and index marking. A binary search on the value survives both rules at O(n log n), a fine fallback. Floyd is what gets you to O(n) time.

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. That 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. The lesson sorts the input in place as a side effect, so copy first if the caller needs the original order.


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

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

Find the Duplicate worked example: the cycle entrance is 2

The duplicate is the entrance because it is reached by two nodes: the last node of the tail (index 3) and the last node of the cycle (index 4). Both store the value 2, 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

  • Finding a repeat you cannot store. When the data is read-only and a set the size of the data is too expensive, the question becomes how to find a repeat in O(1) extra space.
  • Comparing two orderings. Inversion and reverse-pair counts measure how far one ordering is from another, for example two rankings of the same items.
  • Parallel sorting of a permutation. If values are a permutation of a known range, each chunk can be sorted by its own worker and the results concatenated with no merge step. This needs the permutation guarantee.
  • Cycle detection in general. Iterating any function from a start value ends in a cycle. Floyd's algorithm finds it with two variables, and it is the cycle-finding step inside Pollard's rho factoring.

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. Binary search on the value (O(n log n)) is the fallback.
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. Brute force over all pairs is O(n²).
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, for a permutation of 0 … n−1. 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 point 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 the last tail node and the last cycle node both point at it.
  3. Constraints select the algorithm. O(1) space and read-only rule out the set, sorting and marking. Binary search on the value is the O(n log n) fallback, and Floyd is the O(n) answer.
  4. Merge sort counts cheaply. 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.

Core idea: Read the array as a linked list stored in an integer array. From index i, follow the pointer to index nums[i]. Every value lies in 1..n but there are n+1 slots, so some index gets pointed at twice, and the duplicate value is the entry node of a cycle in that pointer graph. Floyd's tortoise-and-hare finds that entry with two integer variables and no writes to the array.

Problem, rephrased

You're auditing a fleet of n+1 machines. Each machine's config names the ID of the machine it forwards traffic to, and every ID named is a real machine in 1..n. So at least one ID is named by two or more machines, and following the forwarding chain eventually loops. The report is an array nums of n+1 integers, each in [1, n], with exactly one value that repeats (it may appear two or more times).

Sign in to continue reading

The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.

Sign in to read the full lesson

Sign in to MAANG.io

Use your Google or Microsoft account — no password to remember.

Continue with Google Continue with Microsoft

Please accept the terms above to continue.