Breaking down today's GFG POTD — simply.
Missing Element in Range
Input: arr[] = [10, 12, 11, 15], low = 10, high = 15
The naive way would be to check every range number against the whole array — that's O(n²) and painful. Instead, I asked: what if lookups were instant? That's exactly what a HashSet gives us.
Store the array in a HashSet. This gives us O(1) lookup for any element instead of scanning the whole array each time.
Walk through the range from low → high. For each number, just check — is it in the HashSet?
If it's NOT in the set, it's missing. Add it to the result list and return.
# Python Solution
class Solution:
def missingRange(self, arr, low, high):
copyArr = set(arr)
result = []
for num in range(low, high + 1):
if num not in copyArr:
result.append(num)
return result
# Time: O(n + range) | Space: O(n)class Solution {
public ArrayList<Integer> missingRange(int[] arr, int low, int high) {
HashSet<Integer> copyArr = new HashSet<>();
for (int x : arr) copyArr.add(x);
ArrayList<Integer> result = new ArrayList<>();
for (int num = low; num <= high; num++) {
if (!copyArr.contains(num)) {
result.add(num);
}
}
return result;
}
}class Solution {
public:
vector<int> missinRange(vector<int>& arr, int low, int high) {
unordered_set<int> copyArr(arr.begin(), arr.end());
vector<int> result;
for (int num = low; num <= high; num++) {
if (copyArr.find(num) == copyArr.end()) {
result.push_back(num);
}
}
return result;
}
};One pass to build set + one pass through range
HashSet stores all array elements
Before writing a second loop, always ask yourself — can a HashSet do this in one pass? Most of the time, it can. The right data structure is often the entire solution.
Follow along with the 60 Days POTD · NPCI × GeeksforGeeks — daily solutions and breakdowns.