Set Mismatch - Practice Coding Problems

Set Mismatch - Problem

You have a set of integers s, which originally contains all the numbers from 1 to n. Unfortunately, due to some error, one of the numbers in s got duplicated to another number in the set, which results in repetition of one number and loss of another number.

You are given an integer array nums representing the data status of this set after the error. Find the number that occurs twice and the number that is missing and return them in the form of an array.

The returned array should contain [duplicate, missing] where duplicate is the number that appears twice and missing is the number that should be present but isn't.

Input & Output

Example 1 — Basic Case

$ Input: nums = [1,2,2,4]

› Output: [2,3]

💡 Note: Number 2 appears twice (duplicate), number 3 is missing from the sequence 1,2,3,4

Example 2 — Different Position

$ Input: nums = [1,1]

› Output: [1,2]

💡 Note: Number 1 appears twice (duplicate), number 2 is missing from the sequence 1,2

Example 3 — Larger Array

$ Input: nums = [3,2,3,4,6,5]

› Output: [3,1]

💡 Note: Number 3 appears twice (duplicate), number 1 is missing from the sequence 1,2,3,4,5,6

Constraints

2 ≤ nums.length ≤ 10⁴
1 ≤ nums[i] ≤ 10⁴

Visualization

Tap to expand

Understanding the Visualization

Perfect Sequence

Should be [1,2,3,4] with each number appearing once

Error Occurs

One number (3) gets replaced by duplicate of another (2)

Find Both

Identify duplicate (2) and missing (3) numbers

Key Takeaway

🎯 Key Insight: Use frequency counting or mathematical sum differences to identify the duplicate (appears twice) and missing (appears zero times) numbers

Asked in

a Amazon 35 G Google 28 M Microsoft 22 🍎 Apple 18

The key insight is that in a perfect sequence 1 to n, exactly one number appears twice and one is missing. Best approach is Hash Map Frequency Count for clarity or Mathematical Sum Difference for optimal space. Time: O(n), Space: O(n) for hash map or O(1) for math approach.

Common Approaches

Approach	Time	Space	Notes
✓ Hash Map Frequency Count	O(n)	O(n)	Use hash map to count frequencies, then find duplicate and missing
Mathematical Sum Difference	O(n)	O(1)	Use sum formulas to calculate duplicate and missing numbers
Brute Force	O(n²)	O(1)	Check each number from 1 to n to count occurrences

Hash Map Frequency Count — Algorithm Steps

Step 1: Count frequency of each number in a hash map
Step 2: Iterate through numbers 1 to n
Step 3: Find number with frequency 2 (duplicate) and missing from map

Visualization

Tap to expand

Step-by-Step Walkthrough

Count Frequencies

Build hash map with frequency of each number

Check 1 to n

Look up each expected number in the map

Find Anomalies

Frequency 2 = duplicate, missing from map = lost number

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void solution(int* nums, int n, int* result) {
    int count[1001] = {0}; // Assuming numbers are <= 1000
    
    // Count frequency of each number
    for (int i = 0; i < n; i++) {
        count[nums[i]]++;
    }
    
    int duplicate = -1;
    int missing = -1;
    
    // Find duplicate and missing
    for (int i = 1; i <= n; i++) {
        if (count[i] == 2) {
            duplicate = i;
        } else if (count[i] == 0) {
            missing = i;
        }
    }
    
    result[0] = duplicate;
    result[1] = missing;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array manually
    int nums[1000];
    int n = 0;
    char* ptr = strchr(line, '[') + 1;
    char* token = strtok(ptr, ",]");
    while (token != NULL) {
        nums[n++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int result[2];
    solution(nums, n, result);
    printf("[%d,%d]\n", result[0], result[1]);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass to count frequencies, then single pass through 1 to n

✓ Linear Growth

Space Complexity

O(n)

Hash map stores up to n key-value pairs

⚡ Linearithmic Space

185.0K Views

Medium Frequency

~15 min Avg. Time

2.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Hash Map Frequency Count — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler