Find the Duplicate Number (Floyd on Array)

🎯

Find the Duplicate Number (Floyd on Array)

mediumTWO_POINTERAmazonFacebookGoogle

Imagine you have a list of IDs where one ID is repeated, but you can't modify the list or use extra space. How do you find the duplicate efficiently?

💡 This problem is about detecting a cycle in a sequence represented by array indices. Beginners often struggle because the array isn't a linked list, but the problem can be transformed into cycle detection using fast and slow pointers.

📋

Problem Statement

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one without modifying the array and using only constant extra space.

1 ≤ n ≤ 10^5nums.length == n + 11 ≤ nums[i] ≤ nOnly one duplicate number exists but it could be repeated more than once

💡

Example

Input"[1,3,4,2,2]"

Output2

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

Input"[3,1,3,4,2]"

Output3

The number 3 is duplicated. The fast and slow pointers meet inside the cycle and then we find the cycle start.

• Array with minimum size (n=1) → duplicate is the only number
• Duplicate number appears multiple times → still find the single duplicate
• Duplicate number is the smallest number (1)
• Duplicate number is the largest number (n)

⚠️

Common Mistakes

Modifying the input array when not allowed

Solution may be rejected or incorrect if input must remain unchanged

✅ Use Floyd's cycle detection which does not modify the array

Using extra space like hash sets when constant space is required

Fails space complexity constraints

✅ Use fast and slow pointers to detect cycle without extra space

Incorrectly initializing pointers or loop conditions in Floyd's algorithm

Infinite loops or wrong answers

✅ Carefully follow the two-phase approach with correct pointer updates

Assuming duplicate appears only twice

Fails on inputs where duplicate appears multiple times

✅ Floyd's algorithm works regardless of duplicate frequency

🧠

Brute Force (Nested Loops)

💡 This approach exists to establish a baseline understanding by checking every pair for duplicates, which is intuitive but inefficient.

Intuition

Check every element against every other element to find if a duplicate exists.

Algorithm

1. Iterate over each element in the array.
2. For each element, iterate over the rest of the array to check for duplicates.
3. If a duplicate is found, return it immediately.
4. If no duplicates found after full iteration, return -1 (though problem guarantees a duplicate).

💡 The nested loops make it easy to understand but hard to scale for large inputs.

</>

Code

def findDuplicate(nums):
    n = len(nums)
    for i in range(n):
        for j in range(i + 1, n):
            if nums[i] == nums[j]:
                return nums[i]
    return -1

# Driver code
if __name__ == '__main__':
    print(findDuplicate([1,3,4,2,2]))  # Output: 2

Line Notes

for i in range(n):Outer loop picks each element to compare

for j in range(i + 1, n):Inner loop compares current element with all subsequent elements

if nums[i] == nums[j]:Check if a duplicate pair is found

return nums[i]Return the duplicate immediately to avoid unnecessary checks

public class Solution {
    public static int findDuplicate(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (nums[i] == nums[j]) {
                    return nums[i];
                }
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] nums = {1,3,4,2,2};
        System.out.println(findDuplicate(nums)); // Output: 2
    }
}

Line Notes

for (int i = 0; i < n; i++) {Outer loop selects each element

for (int j = i + 1; j < n; j++) {Inner loop compares with subsequent elements

if (nums[i] == nums[j]) {Check for duplicate pair

return nums[i];Return duplicate immediately to optimize

#include <iostream>
#include <vector>
using namespace std;

int findDuplicate(vector<int>& nums) {
    int n = nums.size();
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (nums[i] == nums[j]) {
                return nums[i];
            }
        }
    }
    return -1;
}

int main() {
    vector<int> nums = {1,3,4,2,2};
    cout << findDuplicate(nums) << endl; // Output: 2
    return 0;
}

Line Notes

for (int i = 0; i < n; i++) {Outer loop iterates over each element

for (int j = i + 1; j < n; j++) {Inner loop checks for duplicates ahead

if (nums[i] == nums[j]) {Detect duplicate pair

return nums[i];Return duplicate immediately to avoid extra work

function findDuplicate(nums) {
    const n = nums.length;
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            if (nums[i] === nums[j]) {
                return nums[i];
            }
        }
    }
    return -1;
}

// Test
console.log(findDuplicate([1,3,4,2,2])); // Output: 2

Line Notes

for (let i = 0; i < n; i++) {Outer loop picks each element

for (let j = i + 1; j < n; j++) {Inner loop compares with subsequent elements

if (nums[i] === nums[j]) {Check for duplicate

return nums[i];Return duplicate immediately to optimize

⏱

Complexity

TimeO(n^2)

SpaceO(1)

Two nested loops each can run up to n times, resulting in quadratic time.

💡 For n=1000, this means about 1,000,000 comparisons, which is inefficient.

Interview Verdict: TLE / Use only to introduce

This approach is too slow for large inputs but helps understand the problem basics.

🧠

Sorting and One Pass

💡 Sorting the array makes duplicates adjacent, simplifying detection. This approach is faster but modifies the input, which may not be allowed.

Intuition

Sort the array so duplicates appear next to each other, then scan once to find the duplicate.

Algorithm

1. Sort the array in ascending order.
2. Iterate through the sorted array.
3. Compare each element with the next one.
4. Return the element if it equals the next element.

💡 Sorting reduces the problem to a simple linear scan for duplicates.

</>

Code

def findDuplicate(nums):
    nums.sort()
    for i in range(len(nums) - 1):
        if nums[i] == nums[i + 1]:
            return nums[i]
    return -1

# Driver code
if __name__ == '__main__':
    print(findDuplicate([3,1,3,4,2]))  # Output: 3

Line Notes

nums.sort()Sort the array to bring duplicates together

for i in range(len(nums) - 1):Iterate through array except last element

if nums[i] == nums[i + 1]:Check adjacent elements for duplicates

return nums[i]Return the duplicate immediately

import java.util.Arrays;

public class Solution {
    public static int findDuplicate(int[] nums) {
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i] == nums[i + 1]) {
                return nums[i];
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] nums = {3,1,3,4,2};
        System.out.println(findDuplicate(nums)); // Output: 3
    }
}

Line Notes

Arrays.sort(nums);Sort the array to group duplicates

for (int i = 0; i < nums.length - 1; i++) {Iterate through array except last element

if (nums[i] == nums[i + 1]) {Check adjacent elements for duplicates

return nums[i];Return duplicate immediately

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int findDuplicate(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    for (int i = 0; i < (int)nums.size() - 1; i++) {
        if (nums[i] == nums[i + 1]) {
            return nums[i];
        }
    }
    return -1;
}

int main() {
    vector<int> nums = {3,1,3,4,2};
    cout << findDuplicate(nums) << endl; // Output: 3
    return 0;
}

Line Notes

sort(nums.begin(), nums.end());Sort array to bring duplicates together

for (int i = 0; i < (int)nums.size() - 1; i++) {Iterate through array except last element

if (nums[i] == nums[i + 1]) {Check adjacent elements for duplicates

return nums[i];Return duplicate immediately

function findDuplicate(nums) {
    nums.sort((a, b) => a - b);
    for (let i = 0; i < nums.length - 1; i++) {
        if (nums[i] === nums[i + 1]) {
            return nums[i];
        }
    }
    return -1;
}

// Test
console.log(findDuplicate([3,1,3,4,2])); // Output: 3

Line Notes

nums.sort((a, b) => a - b);Sort array numerically to group duplicates

for (let i = 0; i < nums.length - 1; i++) {Iterate through array except last element

if (nums[i] === nums[i + 1]) {Check adjacent elements for duplicates

return nums[i];Return duplicate immediately

⏱

Complexity

TimeO(n log n)

SpaceO(1) or O(log n) depending on sorting implementation

Sorting dominates time complexity; scanning is linear.

💡 For n=100000, sorting takes about 1.5 million operations, which is feasible but modifies input.

Interview Verdict: Accepted if modification allowed

Good improvement but not allowed if input must remain unchanged.

🧠

Floyd's Tortoise and Hare (Cycle Detection)

💡 This approach cleverly treats the array as a linked list where each value points to the next index, detecting a cycle caused by the duplicate number.

Intuition

Use two pointers moving at different speeds to detect a cycle, then find the cycle's entry point which is the duplicate.

Algorithm

1. Initialize two pointers, slow and fast, starting at the first element.
2. Move slow pointer by one step and fast pointer by two steps until they meet inside the cycle.
3. Reset one pointer to the start and move both pointers one step at a time.
4. The point where they meet again is the duplicate number.

💡 The first phase detects a cycle; the second phase finds the cycle's entry point, which corresponds to the duplicate.

</>

Code

def findDuplicate(nums):
    slow = nums[0]
    fast = nums[0]
    # Phase 1: Find intersection point
    while True:
        slow = nums[slow]
        fast = nums[nums[fast]]
        if slow == fast:
            break
    # Phase 2: Find entrance to cycle
    slow = nums[0]
    while slow != fast:
        slow = nums[slow]
        fast = nums[fast]
    return slow

# Driver code
if __name__ == '__main__':
    print(findDuplicate([1,3,4,2,2]))  # Output: 2

Line Notes

slow = nums[0]Initialize slow pointer at first element

fast = nums[0]Initialize fast pointer at first element

slow = nums[slow]Move slow pointer one step

fast = nums[nums[fast]]Move fast pointer two steps

public class Solution {
    public static int findDuplicate(int[] nums) {
        int slow = nums[0];
        int fast = nums[0];
        do {
            slow = nums[slow];
            fast = nums[nums[fast]];
        } while (slow != fast);
        slow = nums[0];
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }
        return slow;
    }

    public static void main(String[] args) {
        int[] nums = {1,3,4,2,2};
        System.out.println(findDuplicate(nums)); // Output: 2
    }
}

Line Notes

int slow = nums[0];Initialize slow pointer at first element

int fast = nums[0];Initialize fast pointer at first element

slow = nums[slow];Move slow pointer one step

fast = nums[nums[fast]];Move fast pointer two steps

#include <iostream>
#include <vector>
using namespace std;

int findDuplicate(vector<int>& nums) {
    int slow = nums[0];
    int fast = nums[0];
    do {
        slow = nums[slow];
        fast = nums[nums[fast]];
    } while (slow != fast);
    slow = nums[0];
    while (slow != fast) {
        slow = nums[slow];
        fast = nums[fast];
    }
    return slow;
}

int main() {
    vector<int> nums = {1,3,4,2,2};
    cout << findDuplicate(nums) << endl; // Output: 2
    return 0;
}

Line Notes

int slow = nums[0];Initialize slow pointer at first element

int fast = nums[0];Initialize fast pointer at first element

slow = nums[slow];Move slow pointer one step

fast = nums[nums[fast]];Move fast pointer two steps

function findDuplicate(nums) {
    let slow = nums[0];
    let fast = nums[0];
    do {
        slow = nums[slow];
        fast = nums[nums[fast]];
    } while (slow !== fast);
    slow = nums[0];
    while (slow !== fast) {
        slow = nums[slow];
        fast = nums[fast];
    }
    return slow;
}

// Test
console.log(findDuplicate([1,3,4,2,2])); // Output: 2

Line Notes

let slow = nums[0];Initialize slow pointer at first element

let fast = nums[0];Initialize fast pointer at first element

slow = nums[slow];Move slow pointer one step

fast = nums[nums[fast]];Move fast pointer two steps

⏱

Complexity

TimeO(n)

SpaceO(1)

Two pointers traverse the array at different speeds, meeting inside the cycle in linear time.

💡 For n=100000, this means roughly 100000 steps, which is efficient and uses constant extra space.

Interview Verdict: Accepted / Optimal

This approach is the best for this problem as it meets all constraints and is efficient.

📊

All Approaches - One-Glance Tradeoffs

💡 In 95% of interviews, code Floyd's cycle detection as it is optimal and meets constraints.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n^2)	O(1)	No	N/A	Mention only - never code
2. Sorting and One Pass	O(n log n)	O(1) or O(log n)	No	N/A	Mention if allowed to modify input
3. Floyd's Tortoise and Hare	O(n)	O(1)	No	Yes (duplicate number)	Code this approach

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Step 1: Clarify problem constraints and assumptions.Step 2: Present brute force approach to show understanding.Step 3: Discuss sorting approach and its limitations.Step 4: Introduce Floyd's cycle detection as optimal solution.Step 5: Code the optimal solution carefully and test.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 10min → Test: 3min. Total ~20min

What the Interviewer Tests

Interviewer tests your problem understanding, ability to optimize, knowledge of cycle detection, and coding accuracy.

Common Follow-ups

• What if there are multiple duplicates? → Floyd's algorithm finds one duplicate; others require different methods.
• Can you solve it without modifying the array and using constant space? → Floyd's algorithm does exactly that.

💡 These follow-ups test your understanding of problem constraints and ability to adapt solutions.

🔍

Pattern Recognition

When to Use

1) Array contains n+1 integers with values 1 to n, 2) Need to find duplicate without modifying array, 3) Constant extra space required, 4) Problem hints at cycle or repeated references

Signature Phrases

'Find the duplicate number without modifying the array''Use constant extra space''Array elements represent indices or pointers'

NOT This Pattern When

Sorting-based duplicate detection or hash set based duplicate detection problems

Similar Problems

Linked List Cycle II - same cycle detection techniqueHappy Number - cycle detection in number transformations

Practice

1. You are given a singly linked list and two integers M and N. The task is to traverse the list, skip M nodes, then delete the next N nodes, and repeat this process until the end of the list. Which algorithmic approach best guarantees an optimal O(n) time and O(1) space solution for this problem?

easy

A. Use a recursive approach that deletes nodes during the unwinding phase of recursion.

B. Use a brute force nested loop approach that for each node checks ahead to delete N nodes repeatedly.

C. Use an iterative two-pointer approach that skips M nodes and deletes N nodes in a single pass.

D. Use a dynamic programming approach to store states of nodes to decide deletion.

Solution

1. Step 1: Understand the problem constraints

   The problem requires skipping M nodes and deleting N nodes repeatedly until the list ends, which suggests a linear traversal.

2. Step 2: Evaluate approaches

   Recursive approaches add extra space due to call stack; brute force nested loops increase time complexity; dynamic programming is unnecessary as no overlapping subproblems exist. The iterative two-pointer approach efficiently traverses once, skipping and deleting nodes in O(n) time and O(1) space.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Iterative two-pointer approach matches optimal time and space complexity [OK]

Hint: Iterative two-pointer approach is linear and space efficient [OK]

Common Mistakes:

• Thinking recursion is optimal despite extra stack space
• Using nested loops causing O(n²) time
• Misapplying DP to a linear traversal problem

2. Consider the following Python code implementing the optimal Happy Number check using a known cycle set. What is the output when the input is 7?

def isHappy(n: int) -> bool:
    cycle_set = {4, 16, 37, 58, 89, 145, 42, 20}

    def get_next(number):
        total_sum = 0
        while number > 0:
            digit = number % 10
            total_sum += digit * digit
            number //= 10
        return total_sum

    while n != 1 and n not in cycle_set:
        n = get_next(n)
    return n == 1

print(isHappy(7))

easy

A. Runtime error due to infinite loop

B. null (function returns no value)

C. true

D. false

Solution

1. Step 1: Trace the sequence starting from 7

   7 -> 49 (4²+9²=16+81=97) -> 97 -> 130 -> 10 -> 1 Detailed steps: 7 -> 49 (4²+9²=16+81=97) 97 -> 130 (9²+7²=81+49=130) 130 -> 10 (1²+3²+0²=1+9+0=10) 10 -> 1 (1²+0²=1+0=1) So it reaches 1.

2. Step 2: Check if the code returns true for n=7

   The loop terminates when n == 1, so the function returns true.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Sequence reaches 1 -> returns true [OK]

Hint: Trace sum-of-squares sequence carefully [OK]

Common Mistakes:

• Miscompute sum of squares leading to wrong cycle detection

3. You are given a singly linked list and need to determine if it contains a cycle (a node that can be reached again by continuously following next pointers). Which approach guarantees detection of a cycle in O(n) time and O(1) space without modifying the node values?

easy

A. Use two pointers moving at different speeds (fast and slow) to detect if they meet inside the list.

B. Sort the linked list and then check for consecutive duplicate nodes.

C. Use dynamic programming to record visited states of nodes.

D. Use a hash set to store visited nodes and check for repeats during traversal.

Solution

1. Step 1: Understand the problem constraints

   The problem requires cycle detection in a linked list with O(1) space and O(n) time, without modifying node values.

2. Step 2: Evaluate each approach

   Hash set uses O(n) space, dynamic programming is not applicable here, and sorting a linked list is O(n log n) and does not detect cycles. The fast and slow pointer approach (Floyd's Cycle Detection) meets all constraints.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Fast and slow pointers detect cycles efficiently [OK]

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

Common Mistakes:

• Confusing cycle detection with sorting or DP approaches
• Assuming hash set is O(1) space

4. Consider the following buggy code snippet for reorderList. Which line contains the subtle bug that can cause infinite loops or cycles when traversing the reordered list?

medium

A. Line with 'if left == right or left.next == right:' missing 'right.next = None' termination

B. Line with 'if not right: return' -- base case missing

C. Line with 'if stop: return' -- premature termination

D. Line with 'left = tmp' -- left pointer not updated correctly

Solution

1. Step 1: Identify termination condition

   The code must set right.next = None when left meets right or adjacent to avoid cycles.

2. Step 2: Locate missing termination

   The commented line misses 'right.next = None', causing the list to form cycles.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing termination causes infinite traversal [OK]

Hint: Always terminate reordered list with null to avoid cycles [OK]

Common Mistakes:

• Forgetting to set right.next = null
• Misplacing stop flag
• Incorrect pointer updates

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