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 for finding the middle node of a linked list, what is the value returned when the input list is 1 -> 2 -> 3 -> 4?

easy

A. 2

B. 3

C. 4

D. 1

Solution

1. Step 1: Trace slow and fast pointers

   Initial: slow=1, fast=1; Iteration 1: slow=2, fast=3; Iteration 2: fast.next is null, loop ends.

2. Step 2: Return slow's value

   Slow points to node with value 3 at loop end.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   For even length, returns second middle node (3) [OK]

Hint: Fast pointer moves twice as fast; slow ends at middle [OK]

Common Mistakes:

• Returning first middle node for even length
• Off-by-one errors in loop condition
• Confusing slow and fast pointer positions

2. Given the following code, what is the output when calling nth_from_end(head, 3) where head is a linked list with values [5, 10, 15, 20]?

easy

A. 5

B. 15

C. 20

D. 10

Solution

1. Step 1: Trace stack contents after traversal

   Stack after pushing nodes: [5, 10, 15, 20]

2. Step 2: Pop n-1=2 times and then pop once more for value

   Pop 1: 20, Pop 2: 15, final pop returns 10 which is the 3rd from end

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   3rd from end in [5,10,15,20] is 10 [OK]

Hint: Stack top is last node; pop n times to get nth from end [OK]

Common Mistakes:

• Off-by-one popping
• Returning node instead of value
• Confusing index from front vs end

3. What is the time complexity of the optimized iterative approach for deleting N nodes after skipping M nodes in a singly linked list of length n? Assume M and N are constants.

medium

A. O(n)

B. O(n * (M + N))

C. O(n^2)

D. O(n + M + N)

Solution

1. Step 1: Identify loop behavior

   The algorithm traverses the list once, moving forward by skipping M nodes and deleting N nodes repeatedly.

2. Step 2: Analyze complexity

   Since M and N are constants, each iteration moves forward by at least M+N nodes, so total steps proportional to n.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Single pass traversal yields O(n) time complexity [OK]

Hint: Constant M, N means linear traversal dominates [OK]

Common Mistakes:

• Mistaking nested loops causing O(n*(M+N))
• Assuming quadratic due to inner loops
• Ignoring that M and N are constants

4. Suppose the problem is modified so that the array elements can be zero, representing no movement, and cycles of length 1 (self-loop) are now considered valid. Which modification to the original fast and slow pointer algorithm correctly handles this variant?

hard

A. Remove the check that breaks when slow == next_index(slow), allowing single-element loops to return True.

B. Add a condition to skip zeros in the outer loop and treat zero jumps as invalid for cycles.

C. Modify the direction check to allow zero as both positive and negative direction to include zero jumps.

D. Use a visited set to track indices and return True if any index is revisited, ignoring direction.

Solution

1. Step 1: Understand new problem constraints

   Zero jumps are allowed and single-element loops are valid cycles.

2. Step 2: Identify necessary algorithm change

   The original code breaks when slow == next_index(slow) to exclude single-element loops; removing this check allows detecting single-element cycles.

3. Step 3: Confirm direction and zero handling

   Zeros represent no movement; allowing them means direction check must still be consistent, but zero jumps can form valid cycles.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Removing single-element loop break correctly detects new valid cycles [OK]

Hint: Allow single-element loops by removing cycle length >1 check [OK]

Common Mistakes:

• Skipping zeros entirely
• Treating zero as both directions
• Ignoring direction consistency

5. Suppose the problem is modified so that the linked list is circular (the last node points back to the head), and you need to remove the nth node from the end. Which approach correctly adapts to this scenario?

hard

A. First detect the cycle length by traversing until you return to the start, then remove the (length - n)th node using two pointers.

B. Use the same recursive backtracking approach without changes; it works for circular lists.

C. Break the cycle by setting the last node's next to None, then apply the standard two-pointer method.

D. Use a hash set to track visited nodes and remove the nth node from the end by counting backwards.

Solution

1. Step 1: Detect cycle length

   In a circular list, length is unknown; traverse until returning to start to find length.

2. Step 2: Use two pointers with known length

   Once length is known, use two pointers with gap n+1 to remove the target node safely.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Cycle length detection is necessary before removal [OK]

Hint: Must find cycle length before applying two-pointer removal [OK]

Common Mistakes:

• Applying recursion blindly on circular list causing infinite recursion
• Breaking cycle without restoring it, altering list structure
• Using hash sets unnecessarily increasing space