Set Mismatch (One Duplicate, One Missing)

📋

Problem

Imagine you receive a list of employee IDs that should be unique and sequential, but due to a data entry error, one ID is duplicated and another is missing. You need to find both the duplicate and the missing ID to fix the records.

Given an array nums representing numbers from 1 to n, where one number is duplicated and one number is missing, find the duplicate and the missing number. Return them as an array [duplicate, missing]. Input: an integer array nums of length n. Output: an integer array of length 2, where the first element is the duplicate number and the second is the missing number.

1 ≤ n ≤ 10^5nums.length == n1 ≤ nums[i] ≤ nExactly one number is duplicated and exactly one number is missing

Edge cases: Array of length 2, e.g. [2, 2] → duplicate=2, missing=1Duplicate is the last number, e.g. [1, 2, 3, 4, 4] → duplicate=4, missing=5Duplicate is the first number, e.g. [1, 1, 3, 4, 5] → duplicate=1, missing=2

</>

IDE

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

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

class Solution {
    public int[] findErrorNums(int[] nums) {
        // Write your solution here
        return new int[2];
    }
}

#include <vector>
using namespace std;

vector<int> findErrorNums(vector<int>& nums) {
    // Write your solution here
    return {};
}

function findErrorNums(nums) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: [2, 2]Returning the duplicate number twice instead of missing number.✅ After finding the duplicate, scan for the missing number by checking which number from 1 to n is absent.

Wrong: [3, 3]Confusing duplicate and missing numbers or returning the same number for both.✅ Ensure to distinguish between the number that appears twice and the number that does not appear at all.

Wrong: [1, 1]Incorrectly assuming the first element is both duplicate and missing.✅ Check all numbers from 1 to n to find the missing number separately from the duplicate.

Wrong: [5, 6]Off-by-one error in identifying missing number; swapped duplicate and missing.✅ Return [duplicate, missing] in correct order and verify indices carefully.

Wrong: Timeout or no outputUsing O(n^2) or sorting approach that is too slow for large inputs.✅ Implement O(n) cyclic sort or frequency count to handle large inputs efficiently.

✓

Test Cases

Focus on handling smallest and largest elements correctly.

Watch out for common algorithmic traps like greedy approaches.

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

t1_01basic

Input[1,2,2,4]

Expected[2,3]

⏱ Performance - must finish in 2000ms

2 is duplicated, 3 is missing in the array [1,2,2,4].

💡 Think about how to detect a duplicate and missing number in a sequence.

💡 Use a frequency count or cyclic sort to identify the duplicate and missing.

💡 Return the duplicate number first, then the missing number as [duplicate, missing].

Why it failed: Incorrect output means the duplicate or missing detection logic is flawed. Fix by ensuring you correctly identify the number appearing twice and the one missing from 1 to n.

✓ Correctly identified the duplicate and missing numbers.

t1_02basic

Input[1,3,3,4,5]

Expected[3,2]

⏱ Performance - must finish in 2000ms

3 is duplicated, 2 is missing in the array [1,3,3,4,5].

💡 Check each number's expected position or count to find anomalies.

💡 A cyclic sort approach can place numbers at their correct indices to spot duplicates.

💡 Return the duplicate first and the missing second as [3, 2].

Why it failed: If output is wrong, likely the algorithm misses the missing number or confuses duplicate detection. Fix by verifying the logic that identifies the missing number after detecting the duplicate.

✓ Correctly found the duplicate and missing numbers.

t2_01edge

Input[2,2]

Expected[2,1]

⏱ Performance - must finish in 2000ms

Array length 2 with duplicate 2 and missing 1.

💡 Consider the smallest array size and how duplicates/missing appear.

💡 Check if your code handles n=2 correctly without index errors.

💡 Ensure the logic works even when the duplicate is the largest number.

Why it failed: Fails on small input size or boundary conditions. Fix by handling arrays of length 2 explicitly or ensuring loops and indices cover this case.

✓ Handles smallest input size correctly.

t2_02edge

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

Expected[4,5]

⏱ Performance - must finish in 2000ms

Duplicate is the last number 4, missing is 5.

💡 Check if your algorithm correctly identifies duplicates at the end of the array.

💡 Verify boundary conditions when the missing number is n (the largest).

💡 Make sure to check all numbers from 1 to n inclusive.

Why it failed: Fails to detect duplicate at the end or missing number equal to n. Fix by ensuring the full range 1 to n is checked after processing.

✓ Correctly identifies duplicates and missing at array boundaries.

t2_03edge

Input[1,1,3,4,5]

Expected[1,2]

⏱ Performance - must finish in 2000ms

Duplicate is the first number 1, missing is 2.

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

💡 Ensure your detection logic does not skip the first element.

💡 Confirm that missing number detection works for numbers near the start.

Why it failed: Fails to detect duplicate at the start or missing number near start. Fix by carefully checking all indices and not skipping the first element.

✓ Correctly detects duplicates and missing numbers at the start.

t3_01corner

Input[1,2,3,5,5]

Expected[5,4]

⏱ Performance - must finish in 2000ms

Duplicate 5 and missing 4; tests greedy approach trap.

💡 Beware of greedy approaches that pick first duplicate found without full check.

💡 Use cyclic sort or frequency count to ensure all numbers are checked.

💡 Fix by scanning entire array to find both duplicate and missing numbers.

Why it failed: Greedy approach fails by stopping early or misidentifying missing number. Fix by completing full scan or using cyclic sort to place numbers correctly.

✓ Correctly handles greedy trap by full verification.

t3_02corner

Input[2,2,2,4,5]

Expectednull

⏱ Performance - must finish in 2000ms

Invalid input with multiple duplicates; tests input validation.

💡 Problem states exactly one duplicate and one missing; check input validity.

💡 If multiple duplicates appear, algorithm should handle or reject gracefully.

💡 Fix by validating input or documenting behavior for invalid inputs.

Why it failed: Algorithm assumes exactly one duplicate; fails or returns incorrect result if multiple duplicates. Fix by adding input validation or clarifying constraints.

✓ Handles or documents behavior on invalid inputs.

t3_03corner

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

Expected[6,5]

⏱ Performance - must finish in 2000ms

Duplicate 6 and missing 5; tests off-by-one errors.

💡 Check indexing carefully to avoid off-by-one errors in range checks.

💡 Ensure missing number detection covers all numbers from 1 to n.

💡 Fix by verifying loops and conditions include all indices and values.

Why it failed: Off-by-one errors cause missing number to be misidentified. Fix by adjusting loop bounds and conditions to cover full range.

✓ Correctly handles off-by-one boundary cases.

t4_01performance

Input[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,99]

Expectednull

⏱ Performance - must finish in 2000ms

n=100 with one duplicate (99) and one missing (100); O(n) solution must complete within 2s.

💡 Brute force O(n^2) approaches will time out on large inputs.

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

💡 Avoid nested loops; use index-based swaps or frequency arrays.

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

✓ Algorithm runs in O(n) time and passes performance test.

Practice

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

easy

A. [4,2]

B. [4]

C. [3,4]

D. [1,4]

Solution

1. Step 1: Trace swaps in the while loop

   Initial array: [2,3,2,1] - i=0: nums[0]=2, correct=1; swap nums[0] and nums[1] -> [3,2,2,1] - i=0: nums[0]=3, correct=2; swap nums[0] and nums[2] -> [2,2,3,1] - i=0: nums[0]=2, correct=1; nums[0]==nums[1], so i=1 - i=1: nums[1]=2, correct=1; nums[1]==nums[1], i=2 - i=2: nums[2]=3, correct=2; nums[2]==nums[2], i=3 - i=3: nums[3]=1, correct=0; swap nums[3] and nums[0] -> [1,2,3,2] - i=3: nums[3]=2, correct=1; nums[3]==nums[1], i=4 (end)

2. Step 2: Identify missing numbers

   Final array: [1,2,3,2] Check indices: - i=0: 1 == 1 - i=1: 2 == 2 - i=2: 3 == 3 - i=3: 2 != 4 -> missing number is 4

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Only 4 is missing from 1 to 4 [OK]

Hint: Trace swaps carefully to find final array [OK]

Common Mistakes:

• Off-by-one in missing number
• Confusing duplicates with missing
• Stopping swaps too early

2. You are given a sorted array of unique positive integers and a positive integer k. You need to find the kth positive integer that is missing from this array. Which algorithmic approach guarantees the most efficient solution in terms of time complexity?

easy

A. Use binary search on the array to find the position where the count of missing numbers reaches k.

B. Use a brute force linear scan counting missing numbers until the kth missing is found.

C. Use dynamic programming to store missing counts and find the kth missing number.

D. Use a greedy approach to iteratively guess missing numbers and verify their presence.

Solution

1. Step 1: Understand the problem constraints

   The array is sorted and contains unique positive integers. We want the kth missing positive number not in the array.

2. Step 2: Identify the optimal approach

   Binary search can be used to find the smallest index where the count of missing numbers is at least k, leveraging the formula missing = arr[mid] - (mid + 1). This yields O(log n) time complexity.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Binary search exploits sorted order and missing count formula [OK]

Hint: Binary search on missing count is optimal [OK]

Common Mistakes:

• Thinking brute force is efficient enough
• Confusing DP with missing count calculation

3. Identify the bug in the following code snippet that attempts to find duplicates using cyclic sort:

medium

A. Line with duplicates.append(nums[i]) repeated twice causing duplicates in output

B. Line calculating correct_index = nums[i] - 1 is off by one

C. Condition if nums[i] != nums[correct_index] should be reversed

D. Incrementing i inside else block causes infinite loop

Solution

1. Step 1: Inspect duplicate appending loop

   Duplicates were appended twice for each mismatch, causing repeated entries. The bug is fixed by removing the repeated append.

2. Step 2: Confirm other lines are correct

   Index calculation and swap condition are correct; incrementing i is proper to avoid infinite loop.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Duplicate elements appear twice in output due to repeated append [OK]

Hint: Check for repeated append calls causing duplicate outputs [OK]

Common Mistakes:

• Infinite loop due to missing i increment
• Off-by-one errors in index calculation
• Incorrect swap condition reversing logic

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

5. Suppose the array can contain duplicate positive integers and you want to find the kth missing positive number. Which modification to the optimal binary search approach is necessary to handle duplicates correctly?

hard

A. No modification needed; binary search works the same with duplicates.

B. Modify the missing count calculation to account for duplicates by counting unique elements only.

C. Preprocess the array to remove duplicates before applying binary search.

D. Use a hash set to track missing numbers instead of binary search.

Solution

1. Step 1: Understand impact of duplicates

   Duplicates break the assumption that arr[i] - (i + 1) equals missing count because indices no longer correspond to unique elements.

2. Step 2: Identify correct fix

   Removing duplicates restores the strictly increasing property needed for binary search and correct missing count calculation.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Preprocessing to unique elements preserves binary search correctness [OK]

Hint: Binary search requires strictly increasing array [OK]

Common Mistakes:

• Assuming duplicates don't affect missing count
• Trying to fix missing count formula without removing duplicates