Set Mismatch (One Duplicate, One Missing)

🎯

Set Mismatch (One Duplicate, One Missing)

easyCYCLIC_SORTAmazonGoogle

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.

💡 This problem is about identifying one duplicated number and one missing number in a sequence. Beginners often struggle because the problem requires detecting two anomalies simultaneously, which can be confusing without a systematic approach like cyclic sort.

📋

Problem Statement

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

💡

Example

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

Output[2, 3]

2 is duplicated, 3 is missing

Input"[3, 2, 3, 4, 6, 5]"

Output[3, 1]

3 is duplicated, 1 is missing

• Array of length 2, e.g. [2, 2] → duplicate=2, missing=1
• Duplicate is the last number, e.g. [1, 2, 3, 4, 4] → duplicate=4, missing=5
• Duplicate is the first number, e.g. [1, 1, 3, 4, 5] → duplicate=1, missing=2
• All numbers except one are in correct order, e.g. [1, 2, 3, 5, 5] → duplicate=5, missing=4

⚠️

Common Mistakes

Not handling the case when the missing number is the last number

Returns incorrect missing number

✅ Add explicit check for last element after sorting or cyclic sort

Swapping without checking if nums[i] == nums[correct]

Infinite loop or incorrect swaps

✅ Add condition to only swap if nums[i] != nums[correct]

Using frequency array of size n instead of n+1

Index out of range errors or missing counts for number n

✅ Initialize frequency array with size n+1 to cover all numbers

Sorting array but not checking for missing number at the end

Misses missing number if it's n

✅ After scanning, check if last number equals n, else missing is n

🧠

Brute Force (Counting Frequencies)

💡 This approach exists to build intuition by directly checking frequencies of each number. It is simple but inefficient, helping beginners understand the problem's requirements before optimizing.

Intuition

Count how many times each number appears. The number that appears twice is the duplicate, and the number that doesn't appear is missing.

Algorithm

1. Create a frequency array of size n+1 initialized to zero.
2. Iterate over nums and increment the frequency for each number.
3. Iterate over frequency array to find the number with frequency 2 (duplicate) and frequency 0 (missing).
4. Return the duplicate and missing numbers.

💡 This algorithm is straightforward but requires extra space and two passes, which is easy to understand but not optimal.

</>

Code

def findErrorNums(nums):
    n = len(nums)
    freq = [0] * (n + 1)
    for num in nums:
        freq[num] += 1
    duplicate = missing = -1
    for i in range(1, n + 1):
        if freq[i] == 2:
            duplicate = i
        elif freq[i] == 0:
            missing = i
    return [duplicate, missing]

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

Line Notes

freq = [0] * (n + 1)Initialize frequency array to count occurrences of each number

for num in nums:Iterate over input to count each number's frequency

if freq[i] == 2:Identify the duplicated number by frequency 2

elif freq[i] == 0:Identify the missing number by frequency 0

import java.util.*;
public class Solution {
    public static int[] findErrorNums(int[] nums) {
        int n = nums.length;
        int[] freq = new int[n + 1];
        for (int num : nums) {
            freq[num]++;
        }
        int duplicate = -1, missing = -1;
        for (int i = 1; i <= n; i++) {
            if (freq[i] == 2) duplicate = i;
            else if (freq[i] == 0) missing = i;
        }
        return new int[]{duplicate, missing};
    }

    public static void main(String[] args) {
        int[] result = findErrorNums(new int[]{1, 2, 2, 4});
        System.out.println(Arrays.toString(result)); // Output: [2, 3]
    }
}

Line Notes

int[] freq = new int[n + 1];Create frequency array to count occurrences

for (int num : nums)Count each number's frequency in input array

if (freq[i] == 2)Detect duplicate number by frequency 2

else if (freq[i] == 0)Detect missing number by frequency 0

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

vector<int> findErrorNums(vector<int>& nums) {
    int n = nums.size();
    vector<int> freq(n + 1, 0);
    for (int num : nums) {
        freq[num]++;
    }
    int duplicate = -1, missing = -1;
    for (int i = 1; i <= n; i++) {
        if (freq[i] == 2) duplicate = i;
        else if (freq[i] == 0) missing = i;
    }
    return {duplicate, missing};
}

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

Line Notes

vector<int> freq(n + 1, 0);Initialize frequency vector to count occurrences

for (int num : nums)Count frequency of each number in input

if (freq[i] == 2)Find duplicate number by frequency 2

else if (freq[i] == 0)Find missing number by frequency 0

function findErrorNums(nums) {
    const n = nums.length;
    const freq = new Array(n + 1).fill(0);
    for (const num of nums) {
        freq[num]++;
    }
    let duplicate = -1, missing = -1;
    for (let i = 1; i <= n; i++) {
        if (freq[i] === 2) duplicate = i;
        else if (freq[i] === 0) missing = i;
    }
    return [duplicate, missing];
}

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

Line Notes

const freq = new Array(n + 1).fill(0);Create frequency array initialized to zero

for (const num of nums)Count occurrences of each number

if (freq[i] === 2)Identify duplicate number by frequency 2

else if (freq[i] === 0)Identify missing number by frequency 0

⏱

Complexity

TimeO(n)

SpaceO(n)

We iterate over the array twice: once to count frequencies and once to find duplicate and missing numbers. Frequency array uses O(n) space.

💡 For n=100,000, this means about 200,000 operations and storing 100,001 integers, which is feasible but not optimal.

Interview Verdict: Accepted but not optimal

This approach works but uses extra space and is not the most efficient. It's useful to understand the problem before optimizing.

🧠

Sorting Based Approach

💡 Sorting helps by placing numbers in order, making it easier to spot duplicates and missing numbers. This approach is more efficient than brute force in space but slower in time.

Intuition

Sort the array and then scan it to find where the duplicate occurs (two same adjacent numbers) and where a number is missing (gap between consecutive numbers).

Algorithm

1. Sort the input array.
2. Iterate through the sorted array to find the duplicate (where nums[i] == nums[i+1]).
3. Check for the missing number by detecting gaps between consecutive numbers or if the last number is missing.
4. Return the duplicate and missing numbers.

💡 Sorting simplifies the problem but costs O(n log n) time. The scanning step is straightforward once sorted.

</>

Code

def findErrorNums(nums):
    nums.sort()
    duplicate = -1
    missing = 1
    for i in range(len(nums) - 1):
        if nums[i] == nums[i + 1]:
            duplicate = nums[i]
        elif nums[i + 1] - nums[i] > 1:
            missing = nums[i] + 1
    if nums[-1] != len(nums):
        missing = len(nums)
    return [duplicate, missing]

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

Line Notes

nums.sort()Sort the array to bring duplicates and missing numbers into order

if nums[i] == nums[i + 1]Detect duplicate by adjacent equal elements

elif nums[i + 1] - nums[i] > 1Detect missing number by gap in sequence

if nums[-1] != len(nums)Check if last number is missing

import java.util.*;
public class Solution {
    public static int[] findErrorNums(int[] nums) {
        Arrays.sort(nums);
        int duplicate = -1, missing = 1;
        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i] == nums[i + 1]) duplicate = nums[i];
            else if (nums[i + 1] - nums[i] > 1) missing = nums[i] + 1;
        }
        if (nums[nums.length - 1] != nums.length) missing = nums.length;
        return new int[]{duplicate, missing};
    }

    public static void main(String[] args) {
        int[] result = findErrorNums(new int[]{1, 2, 2, 4});
        System.out.println(Arrays.toString(result)); // Output: [2, 3]
    }
}

Line Notes

Arrays.sort(nums);Sort the array to order elements

if (nums[i] == nums[i + 1])Find duplicate by checking adjacent elements

else if (nums[i + 1] - nums[i] > 1)Find missing number by detecting gaps

if (nums[nums.length - 1] != nums.length)Check if last number is missing

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

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

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

Line Notes

sort(nums.begin(), nums.end());Sort the array to organize elements

if (nums[i] == nums[i + 1])Detect duplicate by adjacent equality

else if (nums[i + 1] - nums[i] > 1)Detect missing number by gap in sequence

if (nums.back() != (int)nums.size())Check if last number is missing

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

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

Line Notes

nums.sort((a, b) => a - b);Sort the array numerically

if (nums[i] === nums[i + 1])Find duplicate by checking adjacent elements

else if (nums[i + 1] - nums[i] > 1)Find missing number by detecting gaps

if (nums[nums.length - 1] !== nums.length)Check if last number is missing

⏱

Complexity

TimeO(n log n)

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

Sorting takes O(n log n) time, scanning takes O(n). No extra space besides sorting overhead.

💡 For n=100,000, sorting is about 1.5 million operations, which is slower than linear but still acceptable.

Interview Verdict: Accepted, less optimal than cyclic sort

Sorting is a common fallback but not the best for this problem. Useful if cyclic sort is not known.

🧠

Optimal Cyclic Sort Approach

💡 Cyclic sort leverages the fact that numbers are from 1 to n and places each number at its correct index. This approach is optimal in time and space and is a must-know pattern for similar problems.

Intuition

Place each number at the index equal to number-1 by swapping. After this, the index where the number is incorrect reveals the duplicate and missing numbers.

Algorithm

1. Initialize index i = 0.
2. While i < n, if nums[i] != nums[nums[i] - 1], swap nums[i] with nums[nums[i] - 1], else increment i.
3. After sorting, iterate over nums to find the index where nums[i] != i + 1.
4. Return [nums[i], i + 1] as duplicate and missing numbers.

💡 The swapping ensures each number is at its correct position. The mismatch after sorting directly gives the answer.

</>

Code

def findErrorNums(nums):
    i = 0
    n = len(nums)
    while i < n:
        correct = nums[i] - 1
        if nums[i] != nums[correct]:
            nums[i], nums[correct] = nums[correct], nums[i]
        else:
            i += 1
    for i in range(n):
        if nums[i] != i + 1:
            return [nums[i], i + 1]
    return [-1, -1]

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

Line Notes

while i < n:Loop through array to place numbers correctly

correct = nums[i] - 1Calculate correct index for current number

if nums[i] != nums[correct]:Check if current number is at correct position

nums[i], nums[correct] = nums[correct], nums[i]Swap to place number correctly

public class Solution {
    public static int[] findErrorNums(int[] nums) {
        int i = 0, n = nums.length;
        while (i < n) {
            int correct = nums[i] - 1;
            if (nums[i] != nums[correct]) {
                int temp = nums[i];
                nums[i] = nums[correct];
                nums[correct] = temp;
            } else {
                i++;
            }
        }
        for (i = 0; i < n; i++) {
            if (nums[i] != i + 1) return new int[]{nums[i], i + 1};
        }
        return new int[]{-1, -1};
    }

    public static void main(String[] args) {
        int[] result = findErrorNums(new int[]{1, 2, 2, 4});
        System.out.println(java.util.Arrays.toString(result)); // Output: [2, 3]
    }
}

Line Notes

while (i < n)Iterate to place each number at correct index

int correct = nums[i] - 1;Calculate target index for current number

if (nums[i] != nums[correct])Check if swap is needed

nums[i] = nums[correct]; nums[correct] = temp;Swap numbers to correct positions

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

vector<int> findErrorNums(vector<int>& nums) {
    int i = 0, n = nums.size();
    while (i < n) {
        int correct = nums[i] - 1;
        if (nums[i] != nums[correct]) {
            swap(nums[i], nums[correct]);
        } else {
            i++;
        }
    }
    for (int i = 0; i < n; i++) {
        if (nums[i] != i + 1) return {nums[i], i + 1};
    }
    return {-1, -1};
}

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

Line Notes

while (i < n)Loop to place each number at its correct index

int correct = nums[i] - 1;Calculate correct index for current number

if (nums[i] != nums[correct])Check if current number is misplaced

swap(nums[i], nums[correct]);Swap to correct position

function findErrorNums(nums) {
    let i = 0, n = nums.length;
    while (i < n) {
        let correct = nums[i] - 1;
        if (nums[i] !== nums[correct]) {
            [nums[i], nums[correct]] = [nums[correct], nums[i]];
        } else {
            i++;
        }
    }
    for (let i = 0; i < n; i++) {
        if (nums[i] !== i + 1) return [nums[i], i + 1];
    }
    return [-1, -1];
}

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

Line Notes

while (i < n)Iterate to place numbers at correct indices

let correct = nums[i] - 1;Calculate target index for current number

if (nums[i] !== nums[correct])Check if swap is needed

[nums[i], nums[correct]] = [nums[correct], nums[i]];Swap numbers to correct positions

⏱

Complexity

TimeO(n)

SpaceO(1)

Each number is swapped at most once to its correct position, so time is linear. No extra space is used besides variables.

💡 For n=100,000, this means about 100,000 operations, which is very efficient.

Interview Verdict: Accepted and optimal

This is the best approach for this problem, combining efficiency and clarity once understood.

📊

All Approaches - One-Glance Tradeoffs

💡 In most interviews, coding the cyclic sort approach is best as it is optimal and demonstrates strong problem-solving skills.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n)	O(n)	No	Yes	Mention only - never code
2. Sorting Based	O(n log n)	O(1) or O(log n)	No	Yes	Mention as intermediate step
3. Cyclic Sort	O(n)	O(1)	No	Yes	Code this approach

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before your interview. Start by clarifying the problem, then explain the brute force approach, and progressively optimize. Practice coding and testing each approach.

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Describe the brute force approach using frequency counting.Step 3: Discuss sorting as a better but not optimal solution.Step 4: Introduce cyclic sort as the optimal approach.Step 5: Code the cyclic sort solution and test with examples.

Time Allocation

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

What the Interviewer Tests

The interviewer tests your problem understanding, ability to optimize, knowledge of cyclic sort, and coding accuracy.

Common Follow-ups

• What if there are multiple duplicates and missing numbers? → Use extended cyclic sort or hash maps.
• Can you solve it without modifying the input array? → Use extra space or mathematical formulas.

💡 These follow-ups test your ability to generalize and handle constraints like immutability.

🔍

Pattern Recognition

When to Use

1) Input contains numbers from 1 to n, 2) Exactly one duplicate and one missing number, 3) Need to find corrupt pair, 4) Constraints allow in-place modification.

Signature Phrases

'array contains numbers from 1 to n''one number appears twice and one is missing'

NOT This Pattern When

Problems with multiple duplicates or missing numbers or unsorted arrays without constraints require different approaches.

Similar Problems

Find the Duplicate Number - focuses on finding duplicate onlyFirst Missing Positive - finds missing number without duplicates

Practice

1. You are given an unsorted array containing numbers from 1 to n with some numbers possibly missing or duplicated. The task is to rearrange the array so that each number i is placed at index i-1 if it exists. Which algorithmic approach guarantees an optimal O(n) time solution without extra sorting?

easy

A. Use cyclic sort by swapping elements to their correct indices based on their values until all are placed correctly.

B. Sort the array using a built-in sort function and then rearrange elements accordingly.

C. Use dynamic programming to track the placement of each number and build the sorted array.

D. Use a greedy approach that swaps elements to their correct positions until all are placed correctly.

Solution

1. Step 1: Understand the problem constraints

   The problem requires placing numbers 1 to n at indices 0 to n-1 respectively, handling duplicates or missing numbers efficiently.

2. Step 2: Identify the optimal approach

   Cyclic sort swaps elements to their correct positions in O(n) time without extra sorting or DP overhead, unlike greedy or sorting approaches.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Cyclic sort directly places elements by index in one pass [OK]

Hint: Cyclic sort swaps elements to correct indices in O(n) time [OK]

Common Mistakes:

• Confusing greedy swaps with cyclic sort
• Assuming sorting is always needed
• Misapplying DP to placement problems

2. You are given an array containing n distinct numbers taken from the range 0 to n. Exactly one number from this range is missing in the array. Which algorithmic approach guarantees finding the missing number in O(n) time and O(1) space without using extra data structures?

easy

A. Applying a dynamic programming approach to build a state table of present numbers

B. Sorting the array and then scanning for the missing number

C. Using a hash set to track presence of numbers and then checking which is missing

D. Cyclic sort to place each number at its correct index, then scanning for the mismatch

Solution

1. Step 1: Understand problem constraints

   The array contains numbers from 0 to n with one missing; all are distinct.

2. Step 2: Identify approach with O(n) time and O(1) space

   Cyclic sort places each number at its index in one pass, then a single scan finds the missing number efficiently.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Cyclic sort rearranges in-place with linear time and constant space [OK]

Hint: Cyclic sort matches numbers to indices in-place [OK]

Common Mistakes:

• Assuming sorting is always O(n log n)
• Thinking hash sets use O(1) space
• Confusing DP with presence checking

3. Identify the bug in the following cyclic sort implementation that aims to place numbers 1 to n at their correct indices:

def cyclic_sort_buggy(arr):
    i = 0
    n = len(arr)
    while i < n:
        correct_index = arr[i] - 1
        if arr[i] != arr[correct_index]:
            arr[i], arr[correct_index] = arr[correct_index], arr[i]
        i += 1
    return arr

What is the issue causing incorrect output or infinite loops?

medium

A. Incrementing i even after a swap causes some elements to remain misplaced.

B. Not checking if arr[i] is within 1 to n causes index errors.

C. Swapping elements without a temporary variable causes data loss.

D. Using a while loop instead of a for loop causes infinite loops.

Solution

1. Step 1: Analyze loop increment

   i is incremented unconditionally even after swapping, skipping re-check of swapped element.

2. Step 2: Understand impact

   Elements swapped in may still be misplaced but are not checked again, causing incorrect final array or infinite loops.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Increment i only when no swap occurs to ensure correct placement [OK]

Hint: Only increment index if no swap occurs [OK]

Common Mistakes:

• Always incrementing index after swap
• Ignoring index bounds
• Misusing loop constructs

4. What is the time complexity of the cyclic sort approach to find the missing number in an array of size n, and why might some candidates mistakenly think it is higher?

medium

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

B. O(n log n) because of the swaps resembling sorting

C. O(n^2) because nested loops are implied by the swapping inside the while loop

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

Solution

1. Step 1: Identify loop behavior

   The while loop swaps numbers to their correct indices. Each number can be swapped at most once before it is in place.

2. Step 2: Analyze total operations

   Since each swap places a number correctly, total swaps ≤ n, so total time is O(n). No nested full loops occur.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

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

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

Common Mistakes:

• Assuming swaps cause nested loops and O(n^2) time
• Confusing with sorting algorithms that are O(n log n)
• Thinking recursion adds extra space

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