The Two Sneaky Numbers of Digitville - Practice Coding Problems

The Two Sneaky Numbers of Digitville - Problem

In the town of Digitville, there was a list of numbers called nums containing integers from 0 to n - 1. Each number was supposed to appear exactly once in the list, however, two mischievous numbers sneaked in an additional time, making the list longer than usual.

As the town detective, your task is to find these two sneaky numbers. Return an array of size two containing the two numbers (in any order), so peace can return to Digitville.

Input & Output

Example 1 — Basic Case

$ Input: nums = [0,1,1,0]

› Output: [0,1]

💡 Note: The numbers 0 and 1 each appear twice in the array. Both are duplicates that sneaked in.

Example 2 — Different Numbers

$ Input: nums = [0,1,2,3,2,1]

› Output: [1,2]

💡 Note: Numbers 1 and 2 each appear twice. They are the sneaky duplicates we need to find.

Example 3 — Edge Case

$ Input: nums = [7,1,2,3,4,5,6,0,8,9,7,8]

› Output: [7,8]

💡 Note: In this larger array, numbers 7 and 8 appear twice each, making them the duplicates.

Constraints

2 ≤ nums.length ≤ 1000
0 ≤ nums[i] ≤ nums.length - 3

Visualization

Tap to expand

Understanding the Visualization

Input

Array with two duplicate numbers sneaking in

Process

Track seen numbers and identify duplicates

Output

Return the two sneaky duplicate numbers

Key Takeaway

🎯 Key Insight: Use a hash set to track seen numbers - when you encounter a number already in the set, you've found a sneaky duplicate!

Asked in

a Amazon 25 M Microsoft 18

The key insight is to track which numbers we've already seen as we iterate through the array. The best approach uses a hash set to detect duplicates in a single pass with O(n) time and O(n) space complexity.

Common Approaches

Approach	Time	Space	Notes
✓ Single Pass Hash Set	O(n)	O(n)	Use hash set to detect duplicates in a single pass
Brute Force	O(n²)	O(1)	Compare each element with every other element to find duplicates
Hash Map Frequency Count	O(n)	O(n)	Count occurrences of each number using a hash map

Single Pass Hash Set — Algorithm Steps

Step 1: Iterate through array with hash set
Step 2: If number already seen, it's a duplicate
Step 3: Continue until we find both duplicates

Visualization

Tap to expand

Step-by-Step Walkthrough

Scan & Track

Add each number to set, check if already exists

Duplicate Found

When number already in set, add to result

Early Exit

Stop when we find both duplicates

Code -

solution.c — C

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

int* solution(int* nums, int numsSize, int* returnSize) {
    int seen[1000] = {0}; // Assuming values 0-999
    int* result = malloc(2 * sizeof(int));
    int count = 0;
    
    for (int i = 0; i < numsSize; i++) {
        if (seen[nums[i]]) {
            result[count++] = nums[i];
            if (count == 2) {
                *returnSize = 2;
                return result;
            }
        } else {
            seen[nums[i]] = 1;
        }
    }
    
    *returnSize = count;
    return result;
}

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

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through array, hash set operations are O(1)

✓ Linear Growth

Space Complexity

O(n)

Hash set stores up to n unique elements in worst case

⚡ Linearithmic Space

33.0K Views

Medium Frequency

~15 min Avg. Time

892 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

Single Pass Hash Set — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler