Find the Duplicate Number (Cyclic Sort)

📋

Problem

Imagine you have a list of employee IDs where one ID is mistakenly duplicated. You need to find that duplicate quickly without extra space.

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. You must not modify the array and use only constant extra space.

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

Edge cases: Duplicate is the smallest number (e.g., [1,1,2,3,4]) → output 1Duplicate is the largest number (e.g., [1,2,3,4,4]) → output 4Duplicate appears multiple times (e.g., [2,2,2,3,4]) → output 2

</>

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 missing duplicate detection logic.✅ Add condition to check if nums[i] == nums[nums[i]-1] before swapping and return nums[i] immediately.

Wrong: Wrong duplicate number (e.g., 1 instead of 2)Incorrect index mapping or off-by-one errors in cyclic sort swaps.✅ Ensure swaps place nums[i] at index nums[i]-1 and check for duplicates before swapping.

Wrong: Timeout or no outputUsing nested loops or sorting instead of cyclic sort causing O(n^2) or O(n log n) time.✅ Implement cyclic sort with O(n) time complexity and detect duplicates during swaps.

Wrong: Fails on multiple duplicates (e.g., returns wrong number or no duplicate)Assuming duplicates appear only twice or not returning on first duplicate detection.✅ Return duplicate immediately when nums[i] == nums[nums[i]-1] during cyclic sort.

✓

Test Cases

Focus on handling edge cases like duplicates at array boundaries and multiple repetitions.

Watch out for common pitfalls like off-by-one errors and incomplete sorting.

Optimize your solution to linear time to handle large inputs efficiently.

t1_01basic

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

Expected2

⏱ Performance - must finish in 2000ms

The number 2 appears twice, so it is the duplicate.

💡 Consider placing each number at its correct index to detect duplicates.

💡 Use cyclic sort to swap elements until each number is at index equal to its value minus one.

💡 When a number is already at its correct index, but the target index has the same number, that number is the duplicate.

Why it failed: Returned wrong duplicate or no duplicate; likely missed checking if nums[i] == nums[nums[i]-1] before swapping. Fix by adding this check to detect duplicates during cyclic sort.

✓ Correctly identified the duplicate using cyclic sort mechanics.

t1_02basic

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

Expected3

⏱ Performance - must finish in 2000ms

The number 3 appears twice, so it is the duplicate.

💡 Try to place each number at its correct index by swapping.

💡 Detect when a number is already at its correct position to find duplicates.

💡 If nums[i] equals nums[nums[i]-1], return nums[i] as the duplicate.

Why it failed: Incorrect output due to missing duplicate detection before swapping. Add condition to check if nums[i] == nums[nums[i]-1] to identify duplicates.

✓ Duplicate correctly found by detecting repeated placement during cyclic sort.

t2_01edge

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

Expected1

⏱ Performance - must finish in 2000ms

Duplicate is the smallest number 1, appearing twice.

💡 Check if your code handles duplicates at the start of the array.

💡 Ensure cyclic sort swaps correctly even when duplicate is the smallest number.

💡 Detect duplicate by checking if nums[i] == nums[nums[i]-1] before swapping.

Why it failed: Fails to detect duplicate when it is the smallest number due to incorrect index mapping or missing duplicate check before swap. Fix by verifying nums[i] == nums[nums[i]-1] before swapping.

✓ Correctly handles smallest number duplicate edge case.

t2_02edge

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

Expected4

⏱ Performance - must finish in 2000ms

Duplicate is the largest number 4, appearing twice.

💡 Verify your code handles duplicates at the end of the array.

💡 Check boundary conditions for index mapping with largest number.

💡 Detect duplicate by checking if nums[i] == nums[nums[i]-1] before swapping.

Why it failed: Fails to detect duplicate when it is the largest number due to off-by-one errors or missing duplicate check. Fix by ensuring correct index calculation and duplicate detection before swap.

✓ Correctly detects largest number duplicate.

t2_03edge

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

Expected2

⏱ Performance - must finish in 2000ms

Duplicate number 2 appears multiple times.

💡 Make sure your solution handles duplicates repeated more than twice.

💡 Check if your duplicate detection triggers on first repeated occurrence.

💡 Return the duplicate as soon as detected during cyclic sort swaps.

Why it failed: Fails to detect duplicate repeated multiple times due to not returning immediately or incorrect duplicate check. Fix by returning duplicate when nums[i] == nums[nums[i]-1].

✓ Correctly identifies duplicate repeated multiple times.

t3_01corner

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

Expected5

⏱ Performance - must finish in 2000ms

Duplicate is the largest number at the end; tests off-by-one errors in index handling.

💡 Check if your index calculations handle last element correctly.

💡 Verify that you do not access out-of-bound indices during swaps.

💡 Ensure duplicate detection uses nums[i] == nums[nums[i]-1] with valid indices.

Why it failed: Off-by-one error causes index out-of-range or missed duplicate detection. Fix by ensuring index nums[i]-1 is within bounds before accessing.

✓ Handles boundary index correctly and finds duplicate.

t3_02corner

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

Expected3

⏱ Performance - must finish in 2000ms

Duplicate number 3 appears multiple times; tests greedy approach failure.

💡 Beware of greedy approaches that stop after first swap without full cyclic sort.

💡 Complete cyclic sort until all elements are placed or duplicate found.

💡 Detect duplicate by checking if nums[i] == nums[nums[i]-1] before swapping.

Why it failed: Greedy approach fails by not fully sorting or missing duplicates repeated multiple times. Fix by looping until no swaps or duplicate found.

✓ Correctly handles multiple duplicates and full cyclic sort.

t3_03corner

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

Expected2

⏱ Performance - must finish in 2000ms

Tests confusion between 0/1 duplicates and multiple duplicates; only one duplicate number repeated multiple times.

💡 Remember problem states only one duplicate number, repeated multiple times is allowed.

💡 Do not assume duplicates are only twice; detect first repeated occurrence.

💡 Return duplicate immediately when detected during cyclic sort.

Why it failed: Fails by assuming duplicates appear only twice or miscounts duplicates. Fix by returning duplicate on first detection during cyclic sort.

✓ Correctly handles multiple repeated duplicates of the same number.

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,100,50]}

Expectednull

⏱ Performance - must finish in 2000ms

n=100, input size at constraint boundary; O(n) cyclic sort must complete within 2 seconds.

💡 Use cyclic sort for O(n) time complexity.

💡 Avoid nested loops or sorting to prevent TLE.

💡 Detect duplicate during swaps to stop early.

Why it failed: TLE due to using O(n^2) or O(n log n) approach instead of O(n) cyclic sort. Fix by implementing cyclic sort with duplicate detection.

✓ Algorithm runs in O(n) time confirming optimal complexity.

Practice

1. Given the following Python function implementing cyclic sort with extra space, what is the output when the input array is [2, 3, 1]?

def cyclic_sort_extra_space(arr):
    n = len(arr)
    result = [0] * n
    for num in arr:
        if 1 <= num <= n:
            result[num - 1] = num
    return result

print(cyclic_sort_extra_space([2, 3, 1]))

easy

A. [2, 3, 1]

B. [3, 1, 2]

C. [0, 0, 0]

D. [1, 2, 3]

Solution

1. Step 1: Initialize result array

   result = [0, 0, 0], n = 3

2. Step 2: Place each number at index num-1

   num=2 -> result[1]=2; num=3 -> result[2]=3; num=1 -> result[0]=1; final result = [1, 2, 3]

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   All numbers placed at correct indices [OK]

Hint: Index num-1 placement yields sorted array [OK]

Common Mistakes:

• Off-by-one index errors
• Returning original array
• Not initializing result array correctly

2. Identify the bug in the following cyclic sort implementation for finding the corrupt pair:

medium

A. Line 6: Missing increment of i after else condition

B. Line 3: Incorrect initialization of n

C. Line 7: Swap logic is incorrect

D. Line 10: Return statement does not handle all cases

Solution

1. Step 1: Analyze the while loop behavior

   Without incrementing i in the else branch, the loop can get stuck when nums[i] == nums[correct_index], causing infinite loop.

2. Step 2: Identify fix

   Adding i += 1 in the else branch ensures progress and termination.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Infinite loop caused by missing index increment [OK]

Hint: Always increment index if no swap to avoid infinite loops [OK]

Common Mistakes:

• Forgetting to increment index after no swap
• Swapping incorrectly
• Misplaced return statements

3. What is the time complexity of the optimal approach that uses cyclic sort combined with a boolean array to find the first k missing positive numbers in an array of size n?

medium

A. O(n * k) due to nested loops scanning for missing numbers

B. O(n + k) because cyclic sort is O(n) and scanning for missing numbers is O(k)

C. O(n log n) due to sorting inside cyclic sort

D. O(n + k + n*k) due to extra space scanning

Solution

1. Step 1: Analyze cyclic sort complexity

   Cyclic sort runs in O(n) because each number is swapped at most once to its correct position.

2. Step 2: Analyze missing number scanning

   Scanning for missing numbers and filling missing list takes O(k) time, as it may extend beyond array length.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Sum of O(n) + O(k) = O(n + k) [OK]

Hint: Cyclic sort is linear; extra scanning adds O(k) [OK]

Common Mistakes:

• Assuming sorting inside cyclic sort causes O(n log n)
• Confusing nested loops causing O(n*k)
• Ignoring that scanning missing numbers is linear in k

4. What is the time complexity of the optimal cyclic sort approach for finding the duplicate and missing numbers in an array of size n?

medium

A. O(n) with additional O(n) space for frequency tracking

B. O(n log n) due to sorting operations

C. O(n^2) in worst case due to nested swaps

D. O(n) because each element is swapped at most once

Solution

1. Step 1: Identify the loops and swaps

   The while loop runs at most n times, each swap places an element correctly, so total swaps ≤ n.

2. Step 2: Confirm no nested repeated work

   Each element is swapped at most once, so total operations are linear in n.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Linear time complexity confirmed by single pass swaps [OK]

Hint: Each element swapped once -> O(n) time [OK]

Common Mistakes:

• Assuming sorting cost O(n log n)
• Thinking swaps can be quadratic
• Confusing extra space usage

5. Suppose the input array can contain numbers outside the range 1 to n, including negatives and zeros, and duplicates. Which modification to the cyclic sort algorithm ensures correct placement of numbers 1 to n at indices 0 to n-1 while ignoring invalid numbers?

hard

A. Swap elements only if arr[i] is in [1, n] and arr[i] != arr[arr[i] - 1], else increment i.

B. Use an extra array of size n to place valid numbers at index num-1, ignoring invalids.

C. Sort the array first, then remove invalid numbers and duplicates.

D. Ignore duplicates by skipping swaps when arr[i] == arr[arr[i] - 1] without checking range.

Solution

1. Step 1: Understand input constraints

   Input may have invalid numbers (negatives, zeros, > n) and duplicates that break in-place cyclic sort.

2. Step 2: Use extra array for placement

   Creating a separate array of size n and placing valid numbers at index num-1 ensures correct placement ignoring invalids and duplicates.

3. Step 3: Avoid in-place swaps that cause index errors or infinite loops

   Extra space approach is safer and simpler for this variant.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Extra array handles invalid and duplicate numbers cleanly [OK]

Hint: Extra array avoids invalid index and duplicate issues [OK]

Common Mistakes:

• Ignoring invalid range checks
• Trying to fix in-place swaps with invalid numbers
• Not handling duplicates properly