19. Missing Element in Range

✅ GFG solution to Missing Element in Range: find all numbers within a given range not present in array using efficient marking technique. 🚀

The problem can be found at the following link: 🔗 Question Link

🧩 Problem Description

Given an array arr[] of integers and a range [low, high], find all the numbers within the range that are not present in the array. Return the missing numbers in sorted order.

📘 Examples

Example 1

Input: arr[] = [10, 12, 11, 15], low = 10, high = 15
Output: [13, 14]
Explanation: Numbers 13 and 14 lie in the range [10, 15] but are not present in the array.

Example 2

Input: arr[] = [1, 4, 11, 51, 15], low = 50, high = 55
Output: [50, 52, 53, 54, 55]
Explanation: Numbers 50, 52, 53, 54 and 55 lie in the range [50, 55] but are not present in the array.

Example 3

Input: arr[] = [5, 6, 7, 8, 9], low = 1, high = 10
Output: [1, 2, 3, 4, 10]
Explanation: Numbers 1, 2, 3, 4, and 10 are missing from the range [1, 10].

🔒 Constraints

$1 \le \text{arr.size()}, \text{low}, \text{high} \le 10^5$
$1 \le \text{arr}[i] \le 10^5$

✅ My Approach

The optimal solution uses Boolean Array Marking to efficiently track present elements:

Boolean Marking with Range Filtering

Create Marking Array:
- Build a boolean array of size (high - low + 1) initialized to false.
- This represents all positions in the range [low, high].
Mark Present Elements:
- Iterate through the input array.
- For each element x that falls within [low, high], mark present[x - low] = true.
- Ignore elements outside the range (optimization over set approach).
Collect Missing Numbers:
- Iterate through the boolean array.
- For each false position at index i, add low + i to the result.
- The result is automatically sorted due to sequential iteration.
Return Result:
- Return the collected missing numbers.

Key Advantage: This approach only processes elements within the range and provides O(1) lookup and marking time, making it more efficient than set-based approaches for small to medium ranges.

📝 Time and Auxiliary Space Complexity

Expected Time Complexity: O(n + r), where n is the size of the array and r is the range size (high - low + 1). We iterate through the array once to mark present elements O(n), then iterate through the range once to collect missing elements O(r).
Expected Auxiliary Space Complexity: O(r), where r is the range size (high - low + 1). We use a boolean array of size equal to the range, which is more space-efficient than a set when the range is smaller than the array size.

🧑‍💻 Code (C++)

class Solution {
public:
    vector<int> missingRange(vector<int>& arr, int low, int high) {
        vector<bool> present(high - low + 1, false);
        for (int x : arr) {
            if (x >= low && x <= high) present[x - low] = true;
        }
        vector<int> ans;
        for (int i = 0; i <= high - low; i++) {
            if (!present[i]) ans.push_back(low + i);
        }
        return ans;
    }
};

⚡ View Alternative Approaches with Code and Analysis

📊 2️⃣ Set-Based Approach

💡 Algorithm Steps:

Insert all array elements into an unordered set for O(1) average lookup.
Iterate through the range [low, high] sequentially.
For each number, check if it exists in the set.
Collect all numbers not found in the set into result vector.

class Solution {
public:
    vector<int> missingRange(vector<int>& arr, int low, int high) {
        unordered_set<int> s(arr.begin(), arr.end());
        vector<int> ans;
        for (int x = low; x <= high; x++) {
            if (s.find(x) == s.end()) ans.push_back(x);
        }
        return ans;
    }
};

📝 Complexity Analysis:

Time: ⏱️ O(n + r) - Set creation O(n), range iteration O(r)
Auxiliary Space: 💾 O(n) - Set stores all n elements

✅ Why This Approach?

Simple and straightforward implementation
Good when array size is much smaller than range
Intuitive logic flow for beginners

📊 3️⃣ Sorting with Two Pointers

💡 Algorithm Steps:

Sort the input array in ascending order.
Use two pointers: one for the current range number and one for array index.
For each number in [low, high], check if it matches the current array element.
If match found, move array pointer; otherwise, add to missing list.

class Solution {
public:
    vector<int> missingRange(vector<int>& arr, int low, int high) {
        sort(arr.begin(), arr.end());
        vector<int> ans;
        int j = 0, n = arr.size();
        for (int i = low; i <= high; i++) {
            while (j < n && arr[j] < i) j++;
            if (j >= n || arr[j] != i) ans.push_back(i);
        }
        return ans;
    }
};

📝 Complexity Analysis:

Time: ⏱️ O(n log n + r) - Sorting plus range traversal
Auxiliary Space: 💾 O(1) - Excluding output array

✅ Why This Approach?

Space efficient without additional data structures
Natural for problems requiring sorted input
Good when array contains many duplicates

📊 4️⃣ Binary Search on Sorted Array (Optional)

💡 Algorithm Steps:

Sort the input array for binary search capability.
For each number in the range [low, high], perform binary search.
If binary search fails to find the number, add it to result.
Return collected missing numbers.

class Solution {
public:
    vector<int> missingRange(vector<int>& arr, int low, int high) {
        sort(arr.begin(), arr.end());
        vector<int> ans;
        for (int x = low; x <= high; x++) {
            if (!binary_search(arr.begin(), arr.end(), x)) ans.push_back(x);
        }
        return ans;
    }
};

📝 Complexity Analysis:

Time: ⏱️ O(n log n + r log n) - Sorting plus r binary searches
Auxiliary Space: 💾 O(1) - Constant extra space

✅ Why This Approach?

Leverages standard library functions
Good when range is small but array is large
Clean and concise implementation

📊 4️⃣ Optimized Set with Range Pre-filtering

💡 Algorithm Steps:

Create a set but only insert elements that fall within [low, high].
This reduces memory usage when array has many out-of-range elements.
Iterate through range and check against filtered set.
Collect missing numbers into result.

class Solution {
public:
    vector<int> missingRange(vector<int>& arr, int low, int high) {
        unordered_set<int> s;
        for (int x : arr) {
            if (x >= low && x <= high) s.insert(x);
        }
        vector<int> ans;
        for (int i = low; i <= high; i++) {
            if (s.find(i) == s.end()) ans.push_back(i);
        }
        return ans;
    }
};

📝 Complexity Analysis:

Time: ⏱️ O(n + r) - Linear passes through array and range
Auxiliary Space: 💾 O(min(n, r)) - Set size limited by range

✅ Why This Approach?

Memory efficient when many elements are out of range
Combines benefits of set and filtering
Better cache locality than full set

🆚 🔍 Comparison of Approaches

🚀 Approach

⏱️ Time Complexity

💾 Space Complexity

✅ Pros

⚠️ Cons

🎯 Boolean Marking

🟢 O(n + r)

🟢 O(r)

🚀 Fast, predictable memory

💾 High space for large ranges

🔍 Set-Based

🟢 O(n + r)

🟡 O(n)

📖 Simple implementation

💾 Stores all elements

📊 Sorting + Two Pointers

🟡 O(n log n + r)

🟢 O(1)

💾 Space efficient

🐌 Sorting overhead

🔎 Binary Search (Optional)

🔴 O(n log n + r log n)

🟢 O(1)

🎯 Uses standard library

🐌 Repeated binary searches

🔧 Filtered Set

🟢 O(n + r)

🟢 O(min(n,r))

⚡ Memory optimized

🔧 Extra condition checks

🏆 Best Choice Recommendation

🎯 Scenario

🎖️ Recommended Approach

🔥 Performance Rating

🏅 Small to medium range size

🥇 Boolean Marking

★★★★★

📖 Simple implementation needed

🥈 Set-Based

★★★★☆

💾 Memory constrained

🥉 Sorting + Two Pointers

★★★★☆

🎯 Large range, small array

🏅 Filtered Set

★★★★★

☕ Code (Java)

class Solution {
    public ArrayList<Integer> missingRange(int[] arr, int low, int high) {
        boolean[] present = new boolean[high - low + 1];
        for (int x : arr) {
            if (x >= low && x <= high) present[x - low] = true;
        }
        ArrayList<Integer> ans = new ArrayList<>();
        for (int i = 0; i <= high - low; i++) {
            if (!present[i]) ans.add(low + i);
        }
        return ans;
    }
}

🐍 Code (Python)

class Solution:
    def missingRange(self, arr, low, high):
        present = [False] * (high - low + 1)
        for x in arr:
            if low <= x <= high:
                present[x - low] = True
        return [low + i for i in range(high - low + 1) if not present[i]]

🧠 Contribution and Support

For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: 📬 Any Questions?. Let's make this learning journey more collaborative!

⭐ If you find this helpful, please give this repository a star! ⭐

📍Visitor Count

Previous18. Count Inversions Next20. Form the Largest Number

Last updated 8 days ago

hashtag🧩 Problem Description

hashtag📘 Examples

hashtagExample 1

hashtagExample 2

hashtagExample 3

hashtag🔒 Constraints

hashtag✅ My Approach

hashtagBoolean Marking with Range Filtering

hashtag📝 Time and Auxiliary Space Complexity

hashtag🧑‍💻 Code (C++)

hashtag📊 2️⃣ Set-Based Approach

hashtag💡 Algorithm Steps:

hashtag📝 Complexity Analysis:

hashtag✅ Why This Approach?

hashtag📊 3️⃣ Sorting with Two Pointers

hashtag💡 Algorithm Steps:

hashtag📝 Complexity Analysis:

hashtag✅ Why This Approach?

hashtag📊 4️⃣ Binary Search on Sorted Array (Optional)

hashtag💡 Algorithm Steps:

hashtag📝 Complexity Analysis:

hashtag✅ Why This Approach?

hashtag📊 4️⃣ Optimized Set with Range Pre-filtering

hashtag💡 Algorithm Steps:

hashtag📝 Complexity Analysis:

hashtag✅ Why This Approach?

hashtag🆚 🔍 Comparison of Approaches

hashtag🏆 Best Choice Recommendation

hashtag☕ Code (Java)

hashtag🐍 Code (Python)

hashtag🧠 Contribution and Support

hashtag📍Visitor Count

🧩 Problem Description

📘 Examples

Example 1

Example 2

Example 3

🔒 Constraints

✅ My Approach

Boolean Marking with Range Filtering

📝 Time and Auxiliary Space Complexity

🧑‍💻 Code (C++)

📊 2️⃣ Set-Based Approach

💡 Algorithm Steps:

📝 Complexity Analysis:

✅ Why This Approach?

📊 3️⃣ Sorting with Two Pointers

💡 Algorithm Steps:

📝 Complexity Analysis:

✅ Why This Approach?

📊 4️⃣ Binary Search on Sorted Array (Optional)

💡 Algorithm Steps:

📝 Complexity Analysis:

✅ Why This Approach?

📊 4️⃣ Optimized Set with Range Pre-filtering

💡 Algorithm Steps:

📝 Complexity Analysis:

✅ Why This Approach?

🆚 🔍 Comparison of Approaches

🏆 Best Choice Recommendation

☕ Code (Java)

🐍 Code (Python)

🧠 Contribution and Support

📍Visitor Count