Find All Missing Elements of a Range: 3 Approaches Ranked

The “find all missing elements of a range” problem comes down to one decision: do you trade O(n) extra space for the fastest possible scan, or do you sort first and save memory?

Given an array arr[] and a range [lo, hi], the task is to print every integer in that range that doesn’t appear in arr[]. The output is a list of gaps. Three approaches handle this; they differ only on how they track presence.

What the Problem Actually Asks

Before writing any code, two clarifications matter: are the range bounds inclusive, and can arr contain values outside [lo, hi]? Most placement interview versions use inclusive bounds. Handle the edge case where arr is empty: the answer is then every integer from lo to hi.

A concrete example, worked through:

• Input: arr = [1, 3, 5, 4], lo = 1, hi = 6
• Integers in range [1, 6]: 1, 2, 3, 4, 5, 6
• Integers in arr: 1, 3, 4, 5
• Missing integers: 2 and 6

That is the expected output. Notice that duplicates in arr do not change the answer: presence is a boolean, not a count.

A second example with a shifted range:

• Input: arr = [10, 12, 11, 15], lo = 10, hi = 15
• Missing: 13 and 14

The range does not have to start at 1. This distinction matters for choosing the right approach. The in-place technique (Approach 3 below) only handles [1..n] ranges; the HashSet and sorting techniques handle any [lo, hi] pair.

Approach 1: HashSet Lookup

Insert every element of arr into a set. Walk from lo to hi; any value absent from the set is missing. This is the approach most placement interview resources recommend because its complexity is easy to defend and the code is short.

def find_missing(arr, lo, hi):
    seen = set(arr)
    return [i for i in range(lo, hi + 1) if i not in seen]

Complexity

• Time: O(n + (hi - lo + 1)) — one pass to build the set, one pass over the range
• Space: O(n) — the set holds at most n distinct elements

This is the answer TCS NQT and Infosys InfyTQ coding rounds expect. It is readable, obviously correct, and its trade-offs are defensible in one sentence: HashSet gives O(n) lookup at the cost of O(n) extra space.

An equivalent Java version uses a HashSet<Integer> with identical logic. The language doesn’t change the complexity.

When to use

Default to this approach unless the interviewer explicitly says “constant extra space.” Over-engineering by default wastes time and introduces bugs.

Approach 2: Sort First, Then Scan

Sort arr, then walk [lo, hi] with a pointer into the sorted array. Advance the pointer whenever its value is less than the current range value. When the pointer skips past a range value or runs off the end of the array, that value is missing.

def find_missing_sorted(arr, lo, hi):
    arr.sort()
    missing = []
    j = 0
    for val in range(lo, hi + 1):
        while j < len(arr) and arr[j] < val:
            j += 1
        if j >= len(arr) or arr[j] != val:
            missing.append(val)
    return missing

Complexity

• Time: O(n log n + (hi - lo + 1)) — dominated by the sort
• Space: O(1) extra (ignoring the output list; Python’s Timsort is in-place)

Use this when the interviewer says “no extra space” and the range is arbitrary. The two-pointer scan after sorting is a pattern that appears in several other placement problems, so the technique is worth learning regardless.

Handling duplicates

If arr has duplicate values, the pointer advances past them without recording a miss. No special-case code is needed.

Approach 3: In-Place Negative Marking

This is the O(n) time, O(1) space solution, but it comes with a hard restriction: it only works when all values in arr fall in the range [1..n], where n is the length of arr. This is the constraint formalised in LeetCode 448: Find All Numbers Disappeared in an Array.

The idea: treat each value as an index. Walk arr once; at position abs(arr[i]) - 1, flip the stored value negative to mark that index as “seen.” After the full walk, any position i that still holds a positive value means i + 1 is missing.

def find_disappeared(arr):
    for i in range(len(arr)):
        idx = abs(arr[i]) - 1
        if arr[idx] > 0:
            arr[idx] = -arr[idx]
    return [i + 1 for i in range(len(arr)) if arr[i] > 0]

Why abs(arr[i])?

A value may already be negative from a previous marking step. Using the absolute value ensures you read the original index, not a corrupted one. This is the only non-obvious step in the algorithm.

Complexity

• Time: O(n) — two linear passes over arr
• Space: O(1) extra — modifies the input array in place

The restriction matters

This approach does not generalise to arbitrary [lo, hi] ranges. If lo = 5 and hi = 30, the index arithmetic breaks. For placement interviews with arbitrary ranges, fall back to HashSet or sorting. Mentioning this restriction proactively shows the interviewer you understand the algorithm, not just the code.

Complexity Comparison

Approach	Time	Extra Space	Arbitrary range?
HashSet	O(n + range)	O(n)	Yes
Sort + Scan	O(n log n + range)	O(1)	Yes
In-place marking	O(n)	O(1)	No — values must be in [1..n]

For most placement scenarios (array size up to 10^5, range up to 10^6), hashing wins on clarity and speed. The sorting approach is the right answer when the interviewer says “no extra data structures.” In-place marking is the correct answer only for the specific LeetCode 448 variant.

What Placement Interviewers Actually Test Here

The list of missing integers is the least interesting part of this problem. Interviewers at service-tier companies (Wipro, Cognizant, Capgemini) and at product companies hiring for IT jobs for freshers care about three things:

• Do you ask clarifying questions before coding? (Bounds inclusive? Duplicates possible? Values within range?)
• Can you state the complexity before being prompted?
• Do you know when the simpler approach is the better one?

Reaching for in-place marking unprompted, in a 30-minute slot with no space constraint, reads as over-engineering. Start with HashSet. Explain the trade-off in one sentence. Offer the in-place variant only if the interviewer says “constant space.” This pattern (default to the readable solution, then optimise on request) applies across most coding rounds at service-tier and mid-tier product companies. Verbally walking through your reasoning as you code is a consistent differentiator in placement rounds: interviewers hear whether you understand the choice you just made, not just whether the output is correct.

This problem belongs to a family of range-membership questions. Practising find the house numbers between which Noddy can build the largest house builds the same pattern-recognition: scan a numeric range, evaluate a condition at each position, collect the result. Both appear in placement coding sets at similar difficulty levels. For the next step up in algorithmic complexity (problems that combine range reasoning with game theory), the two-player coin game using dynamic programming is a logical progression.

The HashSet and sorting approaches represent the two most common time-space trade-off decisions in placement coding rounds. Getting comfortable making that call quickly, and explaining it aloud, is what separates candidates who clear the coding round from those who don’t. If you’re past the placement prep stage and want to apply the same trade-off reasoning to AI pipelines (where a hash-table lookup becomes a vector index lookup), TinkerLLM at ₹299 is a practical starting point: it’s an LLM playground, not a lecture series, and the intuitions connect directly to what AI engineers handle at scale.