Missing Element in Range

JavaView on GFG

Intuition

Find elements in range [low, high] missing from array. Hashing or sort + scan.

Algorithm

1Store all array elements in a set. Iterate range [low, high]: collect elements not in set.

Common Pitfalls

•O(n + range). Use hashset for O(1) lookups. Output all missing elements in range.

Missing Element in Range.java

Java

// Approach: Compute how many elements from the given array fall in each query range using binary search.
// Time: O((n + q) log n) Space: O(1)
import java.util.*;

class Solution {
    public ArrayList<Integer> missingRange(int[] arr, int low, int high) {
        ArrayList<Integer> ans = new ArrayList<>();
        HashSet<Integer> set = new HashSet<>();
        for (int i : arr)
            set.add(i);
        
        for (int i = low; i <= high; ++i) {
            if (!set.contains(i))
                ans.add(i);
        }
        return ans;
    }
}

Was this solution helpful?