Find Missing Elements — Problem Statement & Solution Guide

ArraysEasyCyclic Sort / Index Hashing

TimeO(n + max(nums))

SpaceO(n)

Problem Description

You are provided with an unsorted array of integers, nums, which may contain duplicate values. The array represents a set of unique identifiers that should theoretically form a contiguous sequence starting from 1 up to the maximum value present in the array. However, some identifiers in this range are missing from the array.

Your task is to identify all integers in the range [1, max(nums)] that do not appear in nums. Return these missing integers as a list sorted in ascending order. If no elements are missing, return an empty list.

Note: The array length is not necessarily equal to the maximum value. The range of interest is strictly defined by the maximum value found in the input array, not the array's length.

DSA Pattern Breakdown

"Find Missing Elements"

easy

WHY DOES IT MATTER?

Detecting missing elements in a numeric sequence is a fundamental pattern for data validation, integrity checks, and synchronization tasks, where gaps often indicate lost or corrupted records.

OPTIMIZATION CHALLENGE

The key insight is to replace repeated linear scans with a constant‑time membership structure (hash set or bitmap), collapsing an O(n·max) brute force into a single pass plus a direct‑access sweep.

REAL-WORLD CONNECTION

In distributed logging systems, each log entry receives a monotonically increasing sequence number; missing numbers signal dropped messages or network partitions, prompting retransmission or alerting mechanisms.

During an interview, first state the naive O(n·max) idea, then immediately propose the hash‑set optimization, and justify its linear complexity while mentioning the edge case where a bitmap could be even tighter if the range is known to be small.

COMPLEXITY AT A GLANCE

⏱ Time:O(n + max(nums))

💾 Space:O(n)

Core Theory — Why This Approach?

The problem reduces to identifying gaps in a numeric range that should be fully populated by the elements of an unsorted array. A naive scan that checks each possible value against the array using linear search leads to O(n·m) time (where m = max(nums)), which quickly becomes infeasible for large inputs because each lookup repeats the entire array traversal. The optimal paradigm leverages constant‑time membership checks via a hash‑based set (or a bitmap when the range is bounded) to collapse the lookup cost to O(1) per value, turning the overall runtime into linear time relative to the size of the input and the numeric range. This shift from repeated scans to a single pass plus a direct‑access structure embodies the classic trade‑off of time versus auxiliary space that underpins many array‑based interview problems.

By inserting every array element into a hash set, we obtain a compact representation of the present identifiers. A subsequent linear sweep from 1 through the maximum value simply queries the set for each integer; any absent query indicates a missing identifier. This two‑phase approach runs in O(n + max) time and O(n) extra space, which is optimal for the general case where the maximum value can be arbitrarily larger than the array length. The algorithm also gracefully handles duplicates because the set automatically discards repeated entries, ensuring each identifier is considered only once.

Alternative in‑place techniques, such as marking visited indices by negating values, rely on the array length matching the numeric range, a condition not guaranteed here. Hence, the hash‑set solution is the most robust and widely applicable, delivering deterministic linear performance without mutating the input.

Interview Questions on This Problem

Q1How would you find all missing numbers in the range [1, N] given an unsorted array that may contain duplicates and where N is the maximum element in the array?

Insert each element into a hash set to achieve O(1) look‑ups, then iterate i from 1 to N and collect i if it is not present in the set. This runs in O(N + n) time and O(n) extra space, handling duplicates naturally.

Q2Can you solve the same problem with O(1) extra space? Under what constraints would that be possible?

O(1) extra space is achievable only when the array length equals the numeric range (i.e., the array contains numbers from 1 to n with possible duplicates) so we can use index‑based marking (negation or swapping). If the maximum value exceeds the array size, a constant‑space solution cannot guarantee linear time because we cannot represent the larger range without additional storage.

Q3What are the trade‑offs between using a hash set versus a boolean bitmap for this problem?

A hash set offers O(1) average insert and lookup with space proportional to the number of distinct elements, making it suitable when the range is large or sparse. A bitmap uses O(max) bits, which can be more memory‑efficient for dense ranges but may be prohibitive if max is huge. Both give linear time, but the bitmap provides deterministic O(1) operations without hash collisions.

Examples

Example 1

Input

nums = [2, 3, 5, 3, 2]

Output

[1, 4]

Explanation: The maximum value in the array is 5. The expected range is [1, 5]. The unique values present are {2, 3, 5}. The integers 1 and 4 are missing from this range. Thus, the output is [1, 4].

Example 2

Input

nums = [1, 2, 3, 4, 5]

Output

[]

Explanation: The maximum value is 5. The range is [1, 5]. All integers from 1 to 5 are present in the array. Therefore, there are no missing elements, and the output is an empty list.

Example 3

Input

nums = [7, 7, 7, 7]

Output

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

Explanation: The maximum value is 7. The range is [1, 7]. The only unique value present is 7. All integers from 1 to 6 are missing. The output is [1, 2, 3, 4, 5, 6].

Example 4

Input

nums = [10, 1, 10, 2, 10, 3]

Output

[4, 5, 6, 7, 8, 9]

Explanation: The maximum value is 10. The range is [1, 10]. The unique values present are {1, 2, 3, 10}. The missing integers are 4, 5, 6, 7, 8, and 9. The output is [4, 5, 6, 7, 8, 9].

Constraints

1 <= nums.length <= 10^5
1 <= nums[i] <= 10^5
The maximum value in nums will not exceed 10^5

Optimal Approach & Strategy

Insert all array elements into a hash set, then iterate from 1 to max(nums) and output numbers not found in the set.

Brute Force Approach

For each integer from 1 to max(nums), scan the entire array to see if it appears; collect those that never appear.

Verified Code Solutions

Language:

JavaScript Solution

Time: O(n + max(nums))

function findMissingElements(nums) {
    const set = new Set(nums);
    const maxVal = Math.max(...nums);
    const missing = [];
    for (let i = 1; i <= maxVal; i++) {
        if (!set.has(i)) missing.push(i);
    }
    return missing;
}

const nums = [2, 3, 5, 3, 2];
const missing = findMissingElements(nums);
console.log(missing);

#include <bits/stdc++.h>
using namespace std;

vector<int> findMissingElements(vector<int>& nums) {
    unordered_set<int> seen;
    int maxVal = 0;
    for (int num : nums) {
        seen.insert(num);
        if (num > maxVal) maxVal = num;
    }
    vector<int> missing;
    for (int i = 1; i <= maxVal; ++i) {
        if (!seen.count(i)) missing.push_back(i);
    }
    return missing;
}

int main() {
    vector<int> nums = {2, 3, 5, 3, 2};
    vector<int> missing = findMissingElements(nums);
    for (int x : missing) cout << x << " ";
    return 0;
}

import java.util.*;

public class Solution {
    public List<Integer> findMissingElements(int[] nums) {
        Set<Integer> seen = new HashSet<>();
        int maxVal = 0;
        for (int num : nums) {
            seen.add(num);
            if (num > maxVal) maxVal = num;
        }
        List<Integer> missing = new ArrayList<>();
        for (int i = 1; i <= maxVal; i++) {
            if (!seen.contains(i)) missing.add(i);
        }
        return missing;
    }

    public static void main(String[] args) {
        int[] nums = {2, 3, 5, 3, 2};
        Solution sol = new Solution();
        List<Integer> missing = sol.findMissingElements(nums);
        System.out.println(missing);
    }
}

def find_missing_elements(nums):
    seen = set(nums)
    max_val = max(nums)
    return [i for i in range(1, max_val + 1) if i not in seen]

nums = [2, 3, 5, 3, 2]
missing = find_missing_elements(nums)
print(missing)

function findMissingElements(nums) {
    const set = new Set(nums);
    const maxVal = Math.max(...nums);
    const missing = [];
    for (let i = 1; i <= maxVal; i++) {
        if (!set.has(i)) missing.push(i);
    }
    return missing;
}

const nums = [2, 3, 5, 3, 2];
const missing = findMissingElements(nums);
console.log(missing);

Asked in Top Tech Interviews

Cognizant

Solve in Interative Editor

Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.

Find Missing Elements Solution

Problem Statement

Input

Output

Input

Output

Input

Output

Input

Output

Constraints

More Arrays

Optimized Approach

Brute Force Approach

Step-by-Step Dry Run

Tested Solutions

Find Missing Elements — Problem Statement & Solution Guide

Problem Description

DSA Pattern Breakdown

Core Theory — Why This Approach?

Interview Questions on This Problem

Examples

Constraints

Optimal Approach & Strategy

Brute Force Approach

Verified Code Solutions

Asked in Top Tech Interviews

Solve in Interative Editor