Example: MissingElementsSortingTraversal in C++

// 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;
}