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. Given the following Python code for reorderList and the input list 1->2->3->4, what is the value of the node pointed to by left after the first merge step in the recursion unwinding?

easy

A. Node with value 3

B. Node with value 2

C. Node with value 4

D. Node with value 1

Solution

1. Step 1: Trace recursion to the end

   Recursion reaches right = None, then unwinds from node 4 back to node 1.

2. Step 2: First merge step during unwinding

   At right=4, left=1, tmp=left.next=2; left.next=4; 4.next=2; left=2 after merge.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   After first merge, left points to node with value 2 [OK]

Hint: left moves forward after merging right node [OK]

Common Mistakes:

• Confusing left pointer update
• Off-by-one in recursion unwind
• Misreading next pointer assignments

2. The following code attempts to detect a cycle in a circular array using the fast-slow pointer approach. Identify the line containing the subtle bug that causes incorrect cycle detection.

medium

A. Line with 'return true' inside while loop returns prematurely

B. Line with 'if slow == fast:' missing cycle length check

C. Line with 'direction = nums[i] > 0' incorrectly sets direction

D. Line with 'nums[marker] = 0' incorrectly marks visited elements

Solution

1. Step 1: Identify cycle detection condition

   The code returns true immediately when slow == fast, but does not check if cycle length > 1.

2. Step 2: Understand why self-loop is invalid

   Cycle of length 1 (self-loop) is invalid; must check if slow != next_index(slow) before returning true.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Missing cycle length check causes false positives [OK]

Hint: Check cycle length > 1 to avoid self-loop false positives [OK]

Common Mistakes:

• Returning true on self-loop cycles
• Mixing directions
• Not marking visited nodes

3. What is the time complexity of the optimal Happy Number detection algorithm that uses a known cycle set and repeatedly computes the sum of squares of digits until it reaches 1 or a cycle number? Assume n is the input number and k is the number of iterations until termination.

medium

A. O(n) because each digit is processed once per iteration

B. O(k * log n) because each iteration processes digits proportional to log n and there are k iterations

C. O(k * n) because sum of squares depends on n itself

D. O(k) because the cycle detection set lookup is constant time and digits are fixed length

Solution

1. Step 1: Identify cost per iteration

   Each iteration computes sum of squares of digits. Number of digits in n is proportional to log n, so each iteration is O(log n).

2. Step 2: Multiply by number of iterations k

   The process repeats k times until reaching 1 or cycle. Total time is O(k * log n).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Sum of digits per iteration is log n, repeated k times -> O(k * log n) [OK]

Hint: Sum of digits cost is O(log n), not O(n) [OK]

Common Mistakes:

• Confusing n with number of digits, assuming O(n) per iteration

4. Identify the bug in the following code snippet for detecting and returning the cycle length in a linked list.

medium

A. Line 11: The length counting loop should start with length = 0 instead of 1.

B. Line 6: slow pointer should move two steps instead of one.

C. Line 7: fast pointer should move one step instead of two.

D. Line 4: The condition should check both fast and fast.next to avoid null pointer errors.

Solution

1. Step 1: Check loop condition for pointer safety

   The loop condition only checks if fast is not null, but fast.next may be null causing runtime error on fast.next.next.

2. Step 2: Confirm other lines are correct

   Slow moves one step, fast moves two steps correctly; length counting starts at 1 correctly.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Missing fast.next check causes null pointer dereference [OK]

Hint: Always check fast and fast.next before advancing fast by two steps [OK]

Common Mistakes:

• Forgetting fast.next check
• Off-by-one in length counting
• Swapping slow and fast pointer steps

5. 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