Find Missing Elements Of A Range In C++ Using Array

Finding missing elements within a specified range from an array is a common problem in programming. This task involves identifying which numbers, from a defined contiguous sequence, are absent from a given collection of numbers. In this article, you will learn various C++ approaches to efficiently solve this problem using arrays and other data structures.

Problem Statement

The challenge is to identify all integers that are missing from a given input array, considering a specific contiguous range of numbers. For instance, if the range is [1, 10] and the array contains numbers like {1, 3, 5, 8}, the goal is to find {2, 4, 6, 7, 9, 10}. This problem often arises in data validation, sequence checking, or database integrity verification where a complete set of values is expected.

Example

Consider an array arr = {10, 12, 11, 15} and a specified range from 10 to 15.

The numbers expected in the range [10, 15] are: 10, 11, 12, 13, 14, 15.

The numbers present in the array are: 10, 11, 12, 15.

The missing elements from the array within this range are: 13, 14.

Background & Knowledge Prerequisites

To effectively understand and implement the solutions, readers should be familiar with:

• C++ Basics: Fundamental syntax, variable declaration, loops (for, while).
• Arrays: Declaration, initialization, and iteration.
• Functions: Defining and calling functions.
• Standard Library Containers: Basic understanding of std::vector and std::unordered_set (for certain approaches).
• Sorting Algorithms: Knowledge of std::sort for one of the approaches.

 

Relevant setup information will include necessary headers like , , , and .

Use Cases or Case Studies

Finding missing elements in a range has several practical applications across various domains:

• Data Validation: Ensuring a sequence of IDs, transaction numbers, or record entries is complete without gaps. For example, checking if all invoices for a day (numbered 1 to 100) are present.
• Resource Allocation: Identifying available slots or resources in a contiguous block. If parking spots are numbered 1-50, finding which spots are currently unoccupied.
• Network Packet Analysis: Detecting missing packets in a sequence where each packet has a unique identifier within a range.
• Game Development: Checking for collected items or completed levels in a linear progression. If a player needs to collect items 1 through 10, finding which ones are still missing.
• Database Integrity: Verifying that a series of primary keys or unique identifiers in a table are continuous and that no records are accidentally deleted or skipped.

 

Solution Approaches

Here are three effective methods to find missing elements of a range in C++ using arrays and related data structures.

Approach 1: Using a Boolean Array (Frequency Array)

This approach uses a boolean array (or a frequency array) to mark the presence of each number within the specified range.

Summary: Create a boolean array whose size covers the entire range. Initialize all elements to false. Iterate through the input array and mark true for each present number in the boolean array. Finally, iterate through the boolean array to find false entries, which correspond to missing numbers.

// MissingElementsBooleanArray
#include <iostream>
#include <vector>
#include <numeric> // For std::iota if needed, though not strictly for this problem
#include <algorithm> // For std::max_element, std::min_element

using namespace std;

// Function to find missing elements using a boolean array
vector<int> findMissingBooleanArray(const vector<int>& arr, int lowerBound, int upperBound) {
    if (lowerBound > upperBound) {
        return {}; // Invalid range
    }

    // Determine the size needed for the boolean array
    // We need indices from lowerBound to upperBound
    // So, size = (upperBound - lowerBound + 1)
    vector<bool> present(upperBound - lowerBound + 1, false);

    // Mark numbers present in the input array
    for (int num : arr) {
        // Only consider numbers within the specified range
        if (num >= lowerBound && num <= upperBound) {
            present[num - lowerBound] = true;
        }
    }

    // Collect missing numbers
    vector<int> missingElements;
    for (int i = 0; i <= upperBound - lowerBound; ++i) {
        if (!present[i]) {
            missingElements.push_back(i + lowerBound);
        }
    }

    return missingElements;
}

int main() {
    // Step 1: Define the input array and the range
    vector<int> numbers = {10, 12, 11, 15, 8, 17};
    int lower = 10;
    int upper = 15;

    cout << "Input array: ";
    for (int num : numbers) {
        cout << num << " ";
    }
    cout << endl;
    cout << "Range: [" << lower << ", " << upper << "]" << endl;

    // Step 2: Call the function to find missing elements
    vector<int> missing = findMissingBooleanArray(numbers, lower, upper);

    // Step 3: Display the results
    cout << "Missing elements in range [" << lower << ", " << upper << "]: ";
    if (missing.empty()) {
        cout << "None";
    } else {
        for (int num : missing) {
            cout << num << " ";
        }
    }
    cout << endl;

    // Example with a different range or array
    vector<int> nums2 = {1, 3, 5};
    int lower2 = 1;
    int upper2 = 5;
    cout << "\\nInput array: ";
    for (int num : nums2) {
        cout << num << " ";
    }
    cout << endl;
    cout << "Range: [" << lower2 << ", " << upper2 << "]" << endl;
    vector<int> missing2 = findMissingBooleanArray(nums2, lower2, upper2);
    cout << "Missing elements in range [" << lower2 << ", " << upper2 << "]: ";
    if (missing2.empty()) {
        cout << "None";
    } else {
        for (int num : missing2) {
            cout << num << " ";
        }
    }
    cout << endl;

    return 0;
}

Run

Sample Output:

Input array: 10 12 11 15 8 17 
Range: [10, 15]
Missing elements in range [10, 15]: 13 14 

Input array: 1 3 5 
Range: [1, 5]
Missing elements in range [1, 5]: 2 4

 

Stepwise Explanation:

1. Initialize present array: A std::vector named present is created. Its size is upperBound - lowerBound + 1 to cover all numbers in the range, and all elements are initialized to false. The index i in present corresponds to the number i + lowerBound.
2. Mark existing numbers: The code iterates through each num in the input arr. If num falls within the lowerBound and upperBound, its corresponding position in the present array (present[num - lowerBound]) is set to true. This effectively marks numbers that are present.
3. Collect missing numbers: Another loop iterates from 0 to upperBound - lowerBound. For each index i, if present[i] is false, it means the number i + lowerBound was not found in the input array and is therefore missing. This number is added to the missingElements vector.
4. Return result: The missingElements vector, containing all identified missing numbers, is returned.

 

Approach 2: Using Sorting and Traversal

This method involves sorting the input array and then iterating through it, comparing each element with an expected value in the range.

Summary: Sort the input array. Iterate through the sorted array. Maintain an expected value, starting from the lowerBound. If the current array element is greater than the expected value, add all numbers from expected up to current_element - 1 (that are within the range) to the missing list. Then update expected. After iterating through the array, add any remaining expected numbers up to upperBound to the missing list.

// MissingElementsSortingTraversal
#include <iostream>
#include <vector>
#include <algorithm> // For std::sort

using namespace std;

// Function to find missing elements by sorting and traversing
vector<int> findMissingSortingTraversal(vector<int> arr, int lowerBound, int upperBound) {
    vector<int> missingElements;
    if (lowerBound > upperBound) {
        return {}; // Invalid range
    }
    if (arr.empty()) {
        // If array is empty, all numbers in range are missing
        for (int i = lowerBound; i <= upperBound; ++i) {
            missingElements.push_back(i);
        }
        return missingElements;
    }

    // Step 1: Sort the input array
    sort(arr.begin(), arr.end());

    int expected = lowerBound;

    // Step 2: Iterate through the sorted array
    for (int num : arr) {
        // Ignore numbers outside the upper bound of the range
        if (num > upperBound) {
            break;
        }

        // Ignore numbers below the lower bound, but update expected if needed
        if (num < lowerBound) {
            continue;
        }

        // If num is greater than expected, elements are missing between expected and num
        while (expected < num) {
            if (expected <= upperBound) { // Ensure missing number is within range
                missingElements.push_back(expected);
            }
            expected++;
        }
        
        // After processing missing numbers, update expected to be one greater than current num
        // Only if num is what we expected or greater (we handled less via the while loop)
        if (num == expected) {
            expected++; // Move to the next expected number
        } else if (num > expected - 1) { // If num appeared before current expected after while loop
             // This case handles duplicates correctly, if num == expected we already incremented
             // If num > expected, it means 'expected' was incremented past num in the loop above
             // or 'num' is a duplicate and we want to move 'expected' past 'num' only once.
             // If num is a duplicate, expected will have incremented past it
        }
    }

    // Step 3: Add any remaining missing elements from `expected` to `upperBound`
    while (expected <= upperBound) {
        missingElements.push_back(expected);
        expected++;
    }

    return missingElements;
}

int main() {
    // Step 1: Define the input array and the range
    vector<int> numbers = {10, 12, 11, 15, 8, 17};
    int lower = 10;
    int upper = 15;

    cout << "Input array: ";
    for (int num : numbers) {
        cout << num << " ";
    }
    cout << endl;
    cout << "Range: [" << lower << ", " << upper << "]" << endl;

    // Step 2: Call the function to find missing elements
    vector<int> missing = findMissingSortingTraversal(numbers, lower, upper);

    // Step 3: Display the results
    cout << "Missing elements in range [" << lower << ", " << upper << "]: ";
    if (missing.empty()) {
        cout << "None";
    } else {
        for (int num : missing) {
            cout << num << " ";
        }
    }
    cout << endl;

    // Example with a different array
    vector<int> nums2 = {1, 2, 4, 6};
    int lower2 = 1;
    int upper2 = 6;
    cout << "\\nInput array: ";
    for (int num : nums2) {
        cout << num << " ";
    }
    cout << endl;
    cout << "Range: [" << lower2 << ", " << upper2 << "]" << endl;
    vector<int> missing2 = findMissingSortingTraversal(nums2, lower2, upper2);
    cout << "Missing elements in range [" << lower2 << ", " << upper2 << "]: ";
    if (missing2.empty()) {
        cout << "None";
    } else {
        for (int num : missing2) {
            cout << num << " ";
        }
    }
    cout << endl;

    // Example with array containing elements outside range and duplicates
    vector<int> nums3 = {5, 2, 8, 1, 5, 0, 10};
    int lower3 = 1;
    int upper3 = 7;
    cout << "\\nInput array: ";
    for (int num : nums3) {
        cout << num << " ";
    }
    cout << endl;
    cout << "Range: [" << lower3 << ", " << upper3 << "]" << endl;
    vector<int> missing3 = findMissingSortingTraversal(nums3, lower3, upper3);
    cout << "Missing elements in range [" << lower3 << ", " << upper3 << "]: ";
    if (missing3.empty()) {
        cout << "None";
    } else {
        for (int num : missing3) {
            cout << num << " ";
        }
    }
    cout << endl;


    return 0;
}

Run

Sample Output:

Input array: 10 12 11 15 8 17 
Range: [10, 15]
Missing elements in range [10, 15]: 13 14 

Input array: 1 2 4 6 
Range: [1, 6]
Missing elements in range [1, 6]: 3 5 

Input array: 5 2 8 1 5 0 10 
Range: [1, 7]
Missing elements in range [1, 7]: 3 4 6 7

 

Stepwise Explanation:

1. Handle empty array and invalid range: Edge cases for empty input array or an invalid range (lowerBound > upperBound) are handled first.
2. Sort array: The input array arr is sorted using std::sort. This ensures that numbers are in ascending order, making sequential checking possible.
3. Initialize expected: An integer expected is initialized to lowerBound. This variable will track the next number we anticipate finding in the array.
4. Iterate and compare: The code iterates through the sorted array arr.
   • It skips numbers that are outside the specified range (< lowerBound or > upperBound).

• If the current num is greater than expected, it means numbers between expected and num (exclusive) are missing. These missing numbers (up to upperBound) are added to missingElements. expected is incremented until it catches up with num.
• If num matches expected (or num is a duplicate that we've already processed, thus expected has already moved past it), expected is simply incremented to look for the next number in the sequence. This ensures duplicates are handled correctly without generating false positives for missing numbers.

1. Append remaining missing numbers: After the loop finishes, if expected is still less than or equal to upperBound, it means all numbers from expected up to upperBound are missing. These are added to missingElements.
2. Return result: The missingElements vector is returned.

 

Approach 3: Using Hashing (std::unordered_set)

Hashing offers a very efficient way to check for the presence of elements, especially when the range is large or the input array is unsorted.

Summary: Insert all elements from the input array into an std::unordered_set. Then, iterate through the numbers from lowerBound to upperBound. For each number in the range, check if it exists in the unordered_set. If not, it's a missing element.

// MissingElementsHashing
#include <iostream>
#include <vector>
#include <unordered_set> // For std::unordered_set

using namespace std;

// Function to find missing elements using an unordered_set
vector<int> findMissingHashing(const vector<int>& arr, int lowerBound, int upperBound) {
    vector<int> missingElements;
    if (lowerBound > upperBound) {
        return {}; // Invalid range
    }

    // Step 1: Insert all elements of the input array into an unordered_set
    unordered_set<int> presentNumbers;
    for (int num : arr) {
        // Only insert numbers that could potentially be in the range
        // This is an optimization; inserting all won't break correctness.
        if (num >= lowerBound && num <= upperBound) {
            presentNumbers.insert(num);
        }
    }

    // Step 2: Iterate through the range and check for missing numbers
    for (int i = lowerBound; i <= upperBound; ++i) {
        if (presentNumbers.find(i) == presentNumbers.end()) {
            // If 'i' is not found in the set, it's missing
            missingElements.push_back(i);
        }
    }

    return missingElements;
}

int main() {
    // Step 1: Define the input array and the range
    vector<int> numbers = {10, 12, 11, 15, 8, 17};
    int lower = 10;
    int upper = 15;

    cout << "Input array: ";
    for (int num : numbers) {
        cout << num << " ";
    }
    cout << endl;
    cout << "Range: [" << lower << ", " << upper << "]" << endl;

    // Step 2: Call the function to find missing elements
    vector<int> missing = findMissingHashing(numbers, lower, upper);

    // Step 3: Display the results
    cout << "Missing elements in range [" << lower << ", " << upper << "]: ";
    if (missing.empty()) {
        cout << "None";
    } else {
        for (int num : missing) {
            cout << num << " ";
        }
    }
    cout << endl;

    // Example with a different array
    vector<int> nums2 = {1, 3, 5, 7, 9};
    int lower2 = 1;
    int upper2 = 10;
    cout << "\\nInput array: ";
    for (int num : nums2) {
        cout << num << " ";
    }
    cout << endl;
    cout << "Range: [" << lower2 << ", " << upper2 << "]" << endl;
    vector<int> missing2 = findMissingHashing(nums2, lower2, upper2);
    cout << "Missing elements in range [" << lower2 << ", " << upper2 << "]: ";
    if (missing2.empty()) {
        cout << "None";
    } else {
        for (int num : missing2) {
            cout << num << " ";
        }
    }
    cout << endl;

    return 0;
}

Run

Sample Output:

Input array: 10 12 11 15 8 17 
Range: [10, 15]
Missing elements in range [10, 15]: 13 14 

Input array: 1 3 5 7 9 
Range: [1, 10]
Missing elements in range [1, 10]: 2 4 6 8 10

 

Stepwise Explanation:

1. Initialize unordered_set: An std::unordered_set named presentNumbers is created. This data structure provides average O(1) time complexity for insertion and lookup.
2. Populate unordered_set: The code iterates through each num in the input arr. Each num is inserted into presentNumbers. Numbers outside the target range can optionally be filtered out here, but inserting them won't affect correctness for this problem since only lowerBound to upperBound will be checked later.
3. Check for missing numbers: A loop iterates from lowerBound to upperBound (inclusive). For each number i in this range, presentNumbers.find(i) is used to check if i exists in the set. If find returns presentNumbers.end() (meaning i was not found), then i is a missing element and is added to missingElements.
4. Return result: The missingElements vector is returned.

 

Conclusion

Identifying missing elements within a specified range from an array can be achieved through several robust C++ approaches. The boolean array method is highly efficient for relatively small and dense ranges. Sorting and traversal is effective when the range is implicit or the input array is sparse, though sorting adds an O(N log N) overhead. For large or sparse ranges, or when quick lookups are paramount, the hashing approach using std::unordered_set provides excellent average-case performance. The choice of method largely depends on the specific constraints of the problem, such as the size of the array, the range of numbers, and performance requirements.

Summary

• Problem: Find integers missing from an array within a defined contiguous range [lowerBound, upperBound].
• Boolean Array (Frequency Array) Approach:
• Uses a std::vector to mark presence.
• Pros: O(N + M) time complexity (N = array size, M = range size), O(M) space.
• Cons: Less suitable for very large ranges due to space requirements.
• Sorting and Traversal Approach:
• Sorts the input array, then iterates while tracking an expected value.
• Pros: Handles unsorted input, good for sparse arrays. O(N log N + M) time complexity (due to sorting). O(1) or O(N) space depending on sorting in-place or copy.
• Cons: Sorting can be slow for very large arrays.
• Hashing (std::unordered_set) Approach:
• Stores array elements in a hash set for quick lookups.
• Pros: O(N + M) average time complexity, efficient for sparse arrays and large ranges.
• Cons: O(N) additional space for the hash set, worst-case O(N*M) time for hash collisions (rare with good hash functions).
• Key Consideration: The optimal approach depends on the size of the input array, the extent of the numerical range, and whether the array contains duplicates or out-of-range numbers.