Find Duplicate and Missing (Two Issues)

📋

Find Duplicate and Missing (Two Issues)

Edge cases:

</>

IDE

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

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

class Solution {
    public int[] findDuplicateMissing(int[] nums) {
        // Write your solution here
        return new int[]{-1, -1};
    }
}

#include <vector>
using namespace std;

vector<int> findDuplicateMissing(vector<int> &nums) {
    // Write your solution here
    return {-1, -1};
}

function findDuplicateMissing(nums) {
    // Write your solution here
    return [-1, -1];
}

Common Bugs to Avoid

Wrong: [3, 3]Returning duplicate number twice instead of missing number.✅ After cyclic sort, scan array to find index i where nums[i] != i+1 and return [nums[i], i+1].

Wrong: [2, 2]Confusing duplicate and missing numbers, returning duplicate for both.✅ Identify missing number as the index + 1 where nums[i] != i+1, not the duplicate.

Wrong: [1, 3]Off-by-one error in indexing causing wrong missing number.✅ Use nums[i] != i+1 condition to find missing number correctly.

Wrong: [2, 1]Greedy approach returning first duplicate found without checking missing number.✅ Complete cyclic sort and scan entire array to find both duplicate and missing.

Wrong: TLEUsing nested loops or sorting approach causing time limit exceeded.✅ Implement O(n) cyclic sort approach with in-place swaps.

✓

Test Cases

Focus on handling minimal and boundary inputs correctly before moving on.

Review your algorithm for common pitfalls like greedy traps and indexing errors.

Optimize your solution to linear time using cyclic sort to handle large inputs efficiently.

t1_01basic

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

Expected[3,4]

⏱ Performance - must finish in 2000ms

3 appears twice, and 4 is missing from the array.

💡 Think about placing each number at its correct index.

💡 Use cyclic sort to detect the duplicate and missing numbers.

💡 After cyclic sort, the index where nums[i] != i+1 gives missing and duplicate.

Why it failed: Returned wrong pair: likely did not correctly identify duplicate and missing after sorting. Fix by verifying nums[i] != i+1 after cyclic sort and returning [duplicate, missing].

✓ Correctly identified duplicate and missing using cyclic sort.

t1_02basic

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

Expected[2,3]

⏱ Performance - must finish in 2000ms

2 appears twice, and 3 is missing from the array.

💡 Check if each number is at its correct index after sorting.

💡 Identify the index where nums[i] != i+1 to find anomalies.

💡 Return the duplicate number found at wrong index and the missing index + 1.

Why it failed: Incorrect output due to missing check for duplicate when nums[i] == nums[nums[i]-1]. Fix by swapping only when nums[i] != nums[nums[i]-1].

✓ Correctly found duplicate and missing by cyclic sort.

t2_01edge

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

Expected[2,1]

⏱ Performance - must finish in 2000ms

Array size 2, duplicate is 2, missing is 1.

💡 Test smallest array size with duplicate and missing.

💡 Check if your code handles minimal input correctly.

💡 Ensure cyclic sort works even when n=2 and duplicates exist.

Why it failed: Fails on minimal input size; likely index out of range or no swap performed. Fix by handling n=2 and ensuring swap logic applies.

✓ Handles minimal array size with duplicate and missing correctly.

t2_02edge

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

Expected[1,2]

⏱ Performance - must finish in 2000ms

Duplicate is the first number 1, missing is 2.

💡 Check if duplicate at start of array is detected.

💡 Verify swap logic does not skip duplicates at beginning.

💡 Return duplicate when nums[i] == nums[nums[i]-1] during cyclic sort.

Why it failed: Fails to detect duplicate at start; likely swaps without checking for duplicates. Fix by adding condition to detect duplicate before swapping.

✓ Correctly detects duplicate at start and missing number.

t2_03edge

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

Expected[4,5]

⏱ Performance - must finish in 2000ms

Duplicate is the last number 4, missing is 5.

💡 Check if duplicate at end of array is detected.

💡 Ensure cyclic sort handles duplicates at last index.

💡 Return correct pair after full array traversal.

Why it failed: Fails to detect duplicate at end; likely stops early or misses last index check. Fix by completing full cyclic sort and final scan.

✓ Correctly detects duplicate at end and missing number.

t2_04edge

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

Expected[2,1]

⏱ Performance - must finish in 2000ms

Missing number is 1, duplicate is 2; tests missing number at start.

💡 Check if missing number 1 is detected correctly.

💡 Verify cyclic sort places numbers at correct indices.

💡 Return duplicate and missing after full array scan.

Why it failed: Fails to detect missing number 1 at start; likely off-by-one or incomplete scan. Fix by scanning entire array after cyclic sort.

✓ Correctly finds missing number 1 and duplicate 2.

t3_01corner

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

Expected[2,1]

⏱ Performance - must finish in 2000ms

Duplicate 2, missing 1; tests greedy approach trap.

💡 Beware of greedy approaches that pick first duplicate found.

💡 Use cyclic sort to place numbers correctly before identifying anomalies.

💡 Check all indices after sorting to find missing and duplicate.

Why it failed: Greedy approach fails by returning first duplicate without checking missing. Fix by performing full cyclic sort and scanning entire array.

✓ Avoids greedy trap; correctly finds duplicate and missing.

t3_02corner

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

Expected[3,2]

⏱ Performance - must finish in 2000ms

Tests off-by-one errors in indexing; duplicate 3, missing 2.

💡 Check indexing carefully: nums[i] should be i+1.

💡 Off-by-one errors cause wrong duplicate/missing detection.

💡 Verify conditions comparing nums[i] and i+1.

Why it failed: Off-by-one error in index comparison causes wrong output. Fix by using nums[i] != i+1 for detection.

✓ Correctly handles indexing and finds duplicate and missing.

t3_03corner

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

Expected[2,4]

⏱ Performance - must finish in 2000ms

Tests confusion between counting duplicates and placement; duplicate 2, missing 4.

💡 Do not count occurrences multiple times; focus on placement.

💡 Cyclic sort places each number at index = number - 1.

💡 Detect duplicate when nums[i] == nums[nums[i]-1] during swap.

Why it failed: Confuses counting duplicates with placement; returns wrong pair. Fix by implementing cyclic sort swap with duplicate check.

✓ Correctly distinguishes duplicate and missing via placement.

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]}

Expectednull

⏱ Performance - must finish in 2000ms

n=100, O(n) cyclic sort must complete within 2 seconds.

💡 Use O(n) cyclic sort to avoid TLE.

💡 Avoid nested loops or sorting O(n log n).

💡 In-place swaps ensure linear time complexity.

Why it failed: TLE due to O(n^2) or O(n log n) approach. Fix by implementing O(n) cyclic sort.

✓ Algorithm runs in O(n) time confirming efficiency.

Practice

1. Given the following code snippet, what is the output when calling findErrorNums([1, 2, 2, 4])?

easy

A. [2, 4]

B. [3, 2]

C. [2, 3]

D. [1, 3]

Solution

1. Step 1: Trace the cyclic sort swaps

   Initial array: [1, 2, 2, 4]. The duplicate 2 causes a swap to place numbers correctly except index 2 which remains 2.

2. Step 2: Identify mismatch after sorting

   After sorting, array is [1, 2, 2, 4]. At index 2, expected 3 but found 2 -> duplicate=2, missing=3.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Output matches expected duplicate and missing pair [OK]

Hint: Mismatch found where index+1 != value after cyclic sort [OK]

Common Mistakes:

• Confusing duplicate and missing order
• Off-by-one errors in indexing
• Returning wrong pair from loop

2. Consider the following buggy code for finding the duplicate number. Which line contains the subtle bug that can cause an infinite loop or incorrect result?

medium

A. Line 7: else: i += 1

B. Line 4: if nums[i] == nums[correct_index]:

C. Line 9: else: nums[i], nums[correct_index] = nums[correct_index], nums[i]

D. Line 2: while i < len(nums):

Solution

1. Step 1: Compare with correct code condition

   The condition should be if nums[i] != nums[correct_index] to decide when to swap.

2. Step 2: Identify effect of wrong condition

   Using == causes swapping only when elements are equal, leading to infinite loops or missed duplicates.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Incorrect condition breaks cyclic sort logic [OK]

Hint: Swap only when elements differ, not when equal [OK]

Common Mistakes:

• Reversing the swap condition causing infinite loops
• Incrementing index incorrectly
• Swapping elements in wrong order

3. What is the time complexity of the optimal cyclic sort approach for finding the smallest missing positive range in an array of length n, and why might some candidates mistakenly think it is higher?

medium

A. O(n log n) because of the sorting-like swaps performed

B. O(n) because each element is swapped at most once to its correct position

C. O(n^2) because nested loops cause repeated scanning

D. O(n) but with O(n) auxiliary space due to recursion stack

Solution

1. Step 1: Analyze the swapping behavior

   Each element is swapped at most once to its correct index, so total swaps ≤ n.

2. Step 2: Understand loop iterations

   The outer while loop increments i only when no swap occurs, ensuring linear total iterations.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Linear time due to bounded swaps and single pass [OK]

Hint: Each element moves at most once -> O(n) time [OK]

Common Mistakes:

• Assuming swaps cause O(n^2)
• Confusing sorting complexity with cyclic sort

4. The following code attempts to find the kth missing positive number using binary search. Which line contains a subtle bug that causes incorrect results when the kth missing number is less than the first element of the array?

medium

A. Line 6: if missing <= k:

B. Line 4: mid = (low + high) // 2

C. Line 8: low = mid + 1

D. Line 10: return k + high + 1

Solution

1. Step 1: Identify the bug in condition

   The condition uses <= instead of < when comparing missing and k. This causes the binary search to move low pointer incorrectly when missing equals k.

2. Step 2: Explain impact on edge cases

   When kth missing is less than arr[0], missing counts start at zero, and using <= causes the search to skip the correct boundary, returning wrong results.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Changing <= to < fixes boundary handling [OK]

Hint: Check strict inequality in binary search condition [OK]

Common Mistakes:

• Using <= instead of <
• Incorrect return formula

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