Find the Duplicate Number (Floyd on Array)

📋

Find the Duplicate Number (Floyd on Array)

Edge cases:

</>

IDE

def findDuplicate(nums: list[int]) -> int:public int findDuplicate(int[] nums)int findDuplicate(vector<int>& nums)function findDuplicate(nums)

def findDuplicate(nums):
    # Write your solution here
    pass

class Solution {
    public int findDuplicate(int[] nums) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int findDuplicate(vector<int>& nums) {
    // Write your solution here
    return 0;
}

function findDuplicate(nums) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: -1Returning -1 when no duplicate found due to incorrect cycle detection or pointer initialization.✅ Ensure pointers start correctly and cycle detection loop runs until pointers meet; do not return -1 prematurely.

Wrong: First repeated number found by scanning (e.g., 1 in [1,3,4,2,2])Using a greedy approach scanning for first duplicate instead of cycle detection.✅ Implement Floyd's Tortoise and Hare algorithm to find cycle entry point instead of scanning.

Wrong: Wrong duplicate number due to off-by-one errors (e.g., returning 4 instead of 3)Incorrect pointer movement or indexing causing wrong cycle entry detection.✅ Check pointer increments: slow moves one step, fast moves two steps; use nums[slow] and nums[fast] as indices properly.

Wrong: Fails on repeated duplicates (e.g., returns wrong number or no cycle detected)Cycle entry detection assumes unique cycle length or mishandles repeated duplicates.✅ After pointers meet, reset one pointer to start and move both one step at a time until they meet again.

Wrong: TLE on large inputsUsing nested loops or sorting instead of O(n) cycle detection.✅ Use Floyd's cycle detection algorithm with two pointers for O(n) time and O(1) space.

✓

Test Cases

Try testing your solution on minimal and repeated duplicates to ensure robustness.

Consider common pitfalls like greedy approaches and off-by-one errors in pointer movement.

Focus on optimizing your solution to linear time using cycle detection to avoid TLE.

t1_01basic

Input{"nums":[1,3,4,2,2]}

Expected2

⏱ Performance - must finish in 2000ms

The number 2 appears twice. Using cycle detection, we find the entry point of the cycle which corresponds to the duplicate.

💡 Think about the array as a linked list where each value points to the next index.

💡 Use Floyd's Tortoise and Hare algorithm to detect the cycle and find its entry point.

💡 Initialize two pointers, move one slow and one fast, then find the intersection and entry point.

Why it failed: Returned wrong duplicate or no duplicate. Ensure to use cycle detection correctly: move slow by one step and fast by two steps until they meet, then find cycle start.

✓ Correctly identified the duplicate using cycle detection.

t1_02basic

Input{"nums":[3,1,3,4,2]}

Expected3

⏱ Performance - must finish in 2000ms

The number 3 appears twice. Cycle detection finds the cycle entry at 3.

💡 Visualize the array as pointers to indices forming a cycle at the duplicate.

💡 Apply Floyd's cycle detection: slow and fast pointers moving at different speeds.

💡 After detecting cycle, reset one pointer to start and move both one step to find duplicate.

Why it failed: Incorrect duplicate found or no cycle detected. Check pointer movement and cycle entry detection logic.

✓ Cycle detection correctly found the duplicate number 3.

t2_01edge

Input{"nums":[1,1]}

Expected1

⏱ Performance - must finish in 2000ms

Minimum size array with n=1, duplicate is the only number 1.

💡 Check behavior when array length is minimal (2 elements).

💡 Cycle detection should handle small arrays without error.

💡 Ensure pointers do not go out of bounds and detect cycle correctly.

Why it failed: Fails on minimal input size; likely pointer initialization or boundary check error. Fix by ensuring pointers start within array bounds.

✓ Handles minimal input size correctly.

t2_02edge

Input{"nums":[2,2,2,2,2]}

Expected2

⏱ Performance - must finish in 2000ms

All elements identical with duplicate number 2 repeated multiple times.

💡 Test with all elements the same to confirm cycle detection finds the single duplicate.

💡 Cycle detection should find the cycle entry even if repeated multiple times.

💡 Pointers will meet quickly; verify cycle entry logic handles this.

Why it failed: Fails on repeated duplicates; possibly cycle entry detection assumes unique cycle length. Fix by correctly resetting one pointer to start and moving both one step.

✓ Correctly finds duplicate even when repeated multiple times.

t2_03edge

Input{"nums":[1,4,6,3,2,5,6]}

Expected6

⏱ Performance - must finish in 2000ms

Duplicate is the largest number n=6 in the array.

💡 Check that the algorithm works when duplicate is the maximum value.

💡 Cycle detection does not depend on duplicate value size, only on cycle formation.

💡 Ensure pointer movement uses values as indices correctly.

Why it failed: Fails when duplicate is largest number; likely index usage error. Fix by using nums[slow] and nums[fast] as indices properly.

✓ Correctly detects duplicate even when it is the largest number.

t2_04edge

Input{"nums":[1,2,3,4,5,6,7,8,9,10,10]}

Expected10

⏱ Performance - must finish in 2000ms

Duplicate is the largest number n=10 in a larger array.

💡 Test boundary with largest duplicate in a bigger array.

💡 Cycle detection should find the cycle entry regardless of array size.

💡 Verify pointer movement and cycle entry detection logic.

Why it failed: Fails on exact boundary with largest duplicate; fix pointer indexing and cycle detection steps.

✓ Handles exact boundary with largest duplicate correctly.

t3_01corner

Input{"nums":[1,2,3,4,5,6,7,8,9,10,5]}

Expected5

⏱ Performance - must finish in 2000ms

Duplicate number 5 appears once; tests greedy approach failure.

💡 Beware of greedy approaches that pick first repeated number without cycle detection.

💡 Cycle detection finds the duplicate by detecting cycle entry, not by sorting or counting.

💡 Use Floyd's algorithm to find cycle start instead of scanning linearly.

Why it failed: Fails due to greedy approach returning first repeated number found by scanning. Fix by implementing cycle detection to find cycle entry.

✓ Correctly finds duplicate using cycle detection, avoiding greedy traps.

t3_02corner

Input{"nums":[2,5,9,6,9,3,8,9,7,1]}

Expected9

⏱ Performance - must finish in 2000ms

Duplicate number 9 appears multiple times; tests confusion between 0/1 knapsack and cycle detection.

💡 Do not confuse this problem with knapsack or other DP problems.

💡 Cycle detection requires pointer movement based on values as indices.

💡 Reset one pointer to start after meeting point to find cycle entry.

Why it failed: Fails due to misunderstanding problem type or incorrect pointer movement. Fix by following Floyd's cycle detection steps precisely.

✓ Correctly identifies duplicate despite multiple occurrences.

t3_03corner

Input{"nums":[3,1,3,4,2]}

Expected3

⏱ Performance - must finish in 2000ms

Tests off-by-one errors in pointer movement and indexing.

💡 Check that indices used for pointers are within array bounds.

💡 Ensure slow and fast pointers move correctly: slow by one step, fast by two steps.

💡 Reset slow pointer to start after meeting point to find cycle entry.

Why it failed: Fails due to off-by-one errors causing index out of range or wrong cycle detection. Fix pointer increments and indexing carefully.

✓ Handles pointer movement and indexing correctly.

t4_01performance

Input{"nums":[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,50]}

Expectednull

⏱ Performance - must finish in 2000ms

Large input with n=99, array length 100, duplicate is 50. Algorithm must run in O(n) time within 2 seconds.

💡 Brute force O(n^2) will time out on large inputs.

💡 Use Floyd's cycle detection with O(n) time and O(1) space.

💡 Avoid sorting or extra data structures to meet performance constraints.

Why it failed: TLE due to using nested loops or sorting. Fix by implementing Floyd's cycle detection algorithm with two pointers.

✓ Algorithm runs in O(n) time and passes performance test.

Practice

1. Given the following code snippet for detecting a circular array loop, what is the return value when the input is nums = [2, -1, 1, 2, 2]?

easy

A. True

B. False

C. Raises an IndexError

D. Infinite loop

Solution

1. Step 1: Trace first iteration starting at index 0

   nums[0]=2 (positive), direction is forward. slow and fast start at 0.

2. Step 2: Move slow and fast pointers

   slow moves to index (0+2)%5=2, fast moves two steps: first to 2, then to (2+1)%5=3. Both nums[2] and nums[3] are positive, direction consistent.

3. Step 3: Next iteration

   slow moves to (2+1)%5=3, fast moves two steps: from 3 to (3+2)%5=0, then from 0 to (0+2)%5=2. slow=3, fast=2, not equal yet.

4. Step 4: Next iteration

   slow moves to (3+2)%5=0, fast moves two steps: from 2 to (2+1)%5=3, then from 3 to (3+2)%5=0. slow=0, fast=0, pointers meet.

5. Step 5: Check cycle length

   Check if slow == next_index(slow): next_index(0) = 2, not equal, so cycle length > 1.

6. Final Answer:

   Option A -> Option A

7. Quick Check:

   Cycle detected with consistent direction and length > 1 [OK]

Hint: Pointers meet at index 0 with valid cycle -> returns True [OK]

Common Mistakes:

• Confusing slow and fast pointer positions
• Ignoring direction check
• Mistaking single-element loop as valid

2. You are given a problem where you repeatedly transform a number by replacing it with the sum of the squares of its digits. The goal is to determine if this process eventually reaches 1 or falls into a repeating cycle. Which algorithmic approach is best suited to efficiently detect cycles in this implicit sequence without extra space?

easy

A. Dynamic Programming with memoization to store intermediate results

B. Breadth-First Search (BFS) to explore all possible transformations

C. Greedy approach to pick the next number with the smallest digit sum

D. Floyd's Cycle Detection (Fast and Slow Pointers) to detect cycles in sequences

Solution

1. Step 1: Understand the problem as detecting cycles in a sequence generated by a function

   The problem involves repeatedly applying a function to a number to generate a sequence. Detecting if this sequence reaches 1 or cycles indefinitely is a classic cycle detection problem.

2. Step 2: Identify Floyd's Cycle Detection as the optimal approach

   Floyd's fast and slow pointers efficiently detect cycles in sequences without extra space, unlike DP or BFS which require additional memory or are not suited for implicit sequences.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Cycle detection in implicit sequences -> Floyd's algorithm [OK]

Hint: Cycle detection in sequences -> Floyd's fast-slow pointers [OK]

Common Mistakes:

• Confusing cycle detection with DP or BFS approaches

3. You are given a singly linked list and need to determine the length of a cycle if one exists. Which approach guarantees an optimal solution with O(n) time and O(1) space complexity?

easy

A. Use dynamic programming to store cycle lengths for sublists and combine results.

B. Use a hash set to store visited nodes and count cycle length upon revisiting a node.

C. Use two pointers moving at different speeds to detect the cycle and then count its length by traversing the cycle once.

D. Use a recursive depth-first search to detect cycles and count their lengths.

Solution

1. Step 1: Understand the problem constraints

   The problem requires detecting a cycle and counting its length efficiently in a linked list.

2. Step 2: Evaluate approaches for time and space complexity

   Using two pointers (fast and slow) allows cycle detection in O(n) time and O(1) space, then counting the cycle length by traversing the cycle once is optimal.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Fast-slow pointer approach is classic for cycle detection with constant space [OK]

Hint: Fast-slow pointers detect cycles in O(1) space [OK]

Common Mistakes:

• Believing hash sets are optimal due to extra space
• Confusing DP with cycle detection
• Using recursion unnecessarily

4. You are given a singly linked list and need to determine if it reads the same forwards and backwards. Which approach guarantees an optimal solution with O(n) time and O(1) space complexity?

easy

A. Use fast and slow pointers to find the middle, reverse the second half in-place, then compare both halves.

B. Convert the linked list to an array and check palindrome by comparing elements from both ends.

C. Use a hash set to store visited nodes and check for palindrome by comparing values.

D. Use a recursive approach to compare nodes from start and end simultaneously.

Solution

1. Step 1: Identify the problem constraints

   The problem requires checking palindrome in O(n) time and O(1) space.

2. Step 2: Evaluate approaches

   Converting to array uses O(n) space, recursion uses O(n) stack space, and hash set is not suitable for palindrome check. Using fast and slow pointers to reverse second half in-place meets both time and space requirements.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Optimal approach uses fast-slow pointers and in-place reversal [OK]

Hint: Optimal palindrome check uses fast-slow pointers and in-place reversal [OK]

Common Mistakes:

• Assuming array conversion is optimal due to simplicity
• Believing recursion uses constant space
• Using hash sets for palindrome detection

5. If the linked list nodes cannot be modified (no extra fields allowed) and you want to detect a cycle in O(1) space, which approach correctly adapts Floyd's cycle detection algorithm to also find the entry point of the cycle?

hard

A. Use a hash set to store nodes and find the first repeated node as the cycle start.

B. Modify node values temporarily to mark visited nodes and revert after detection.

C. After detecting the cycle, reset slow to head and move both pointers one step at a time until they meet; the meeting point is the cycle start.

D. Run the fast pointer twice as fast until it reaches the end, then backtrack to find the cycle start.

Solution

1. Step 1: Detect cycle using fast and slow pointers

   When fast and slow meet, a cycle exists but the meeting point is not necessarily the cycle start.

2. Step 2: Find cycle entry point

   Reset slow to head, then move slow and fast one step at a time; their meeting point is the cycle start node.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Standard Floyd's algorithm extension for cycle entry detection [OK]

Hint: Reset slow to head after detection to find cycle start [OK]

Common Mistakes:

• Using extra memory when O(1) space required
• Modifying node values disallowed
• Incorrect pointer movement after detection