Check if an Array Contains All Elements of a Range

Title: Check if an Array Contains All Elements of a Range

In this guide, you’ll learn how to check whether an array contains every integer in a given range [low, high]. This comes up in interviews whenever you need to confirm that a dataset has no gaps, for example verifying that a batch of ticket numbers, sequence IDs, or test case indices is fully covered. We’ll build an O(n) solution, trace it by hand, and work through the edge cases an interviewer expects you to catch.

Understanding the Problem

Given an array arr of integers and two bounds low and high, we need to determine whether every integer from low to high (inclusive) appears at least once somewhere in arr. The array can contain duplicates and values outside the range; those extra values are simply ignored.

This is different from checking whether the array is a sorted, contiguous run. The values just need to be present somewhere in the array, in any order, possibly with other unrelated values mixed in.

Approach / Algorithm Steps

1. Validate that low is not greater than high; if it is, the range is invalid.
2. Compute rangeSize = high - low + 1 and allocate a boolean array present of that size, one slot per target value.
3. Track a counter remaining initialized to rangeSize, the number of target values not yet seen.
4. Scan arr once; for each value that falls inside [low, high] and has not been marked yet, set present[value - low] = true and decrement remaining.
5. If remaining reaches zero during the scan, every target value has been found, so return true immediately.
6. After the scan finishes, return true only if remaining is zero; otherwise at least one value in the range was never seen.

Java Program

public class CheckRangeCoverage {

    public static boolean containsAllElementsInRange(int[] arr, int low, int high) {
        if (low > high) {
            throw new IllegalArgumentException("low cannot be greater than high");
        }

        int rangeSize = high - low + 1;
        boolean[] present = new boolean[rangeSize];
        int remaining = rangeSize;

        for (int value : arr) {
            if (value >= low && value <= high && !present[value - low]) {
                present[value - low] = true;
                remaining--;
                if (remaining == 0) {
                    return true;
                }
            }
        }

        return remaining == 0;
    }

    public static void main(String[] args) {
        int[] arr = {4, 6, 2, 5, 3, 7, 1, 8};
        int low = 2;
        int high = 6;

        boolean result = containsAllElementsInRange(arr, low, high);
        System.out.println("Array contains all elements in range [" + low + ", " + high + "]: " + result);
    }
}

Explanation of the Program

The method containsAllElementsInRange treats the range as a checklist. present[value - low] is the checkbox for value, and remaining is how many boxes are still unchecked.

• rangeSize and the present array shift every target value down by low so it maps to a valid index starting at zero.
• The loop condition value >= low && value <= high filters out values that are not part of the range, so they are simply skipped.
• The !present[value - low] check avoids double-decrementing remaining when the same target value appears more than once in arr.
• Returning early the moment remaining hits zero avoids scanning the rest of a large array once full coverage is already confirmed.
• If the loop finishes without remaining reaching zero, the final return remaining == 0 reports that the range was not fully covered.

Step-by-Step Trace

Trace containsAllElementsInRange(arr, 7, 9) on arr = {7, 2, 9, 7, 8, 1}, where the target range is [7, 9] (three values: 7, 8, 9):

At the end of each iteration, remaining holds the count of values in [low, high] that have not yet appeared in arr[0..i]; once it reaches zero the method returns immediately without looking at arr[5] = 1.

Examples

Example 1: Full Coverage

int[] arr = {4, 6, 2, 5, 3, 7, 1, 8};
boolean result = containsAllElementsInRange(arr, 2, 6);
// result -> true (2, 3, 4, 5, 6 all appear in arr)

Example 2: Missing Values

int[] arr = {10, 20, 30, 40};
boolean result = containsAllElementsInRange(arr, 15, 35);
// result -> false (15, 25, and 35 never appear in arr)

Example 3: Negative Range

int[] arr = {-3, -2, -1, 0, 1};
boolean result = containsAllElementsInRange(arr, -3, 1);
// result -> true (every integer from -3 to 1 is present)

Common Mistakes to Avoid

These are the mistakes that most often turn this problem into a bug hunt during an interview:

• Sizing present[] with arr.length - allocating new boolean[arr.length] instead of new boolean[high - low + 1] either wastes memory or throws ArrayIndexOutOfBoundsException when the range is larger than the array. Size the array from the range, not the input.
• Indexing with the raw value - using present[value] instead of present[value - low] breaks as soon as low is not zero, producing a negative index for values below low. Always subtract low before indexing.
• Off-by-one on rangeSize - computing high - low instead of high - low + 1 silently drops the last value in the range, so a fully covered array can incorrectly report missing coverage. Remember the range is inclusive on both ends.
• Double-decrementing remaining - decrementing remaining every time a value in range is seen, without checking present[] first, undercounts because duplicate values in arr get counted more than once. Only decrement on the first sighting of each value.
• Skipping the low > high check - passing an inverted range straight into high - low + 1 produces a negative array size and a NegativeArraySizeException instead of a clear error. Validate the range before allocating.

Edge Cases to Test

Walk through these inputs before calling the solution complete:

• Empty array
• Range larger than the array's length
• Single-value range (low == high)
• Invalid range (low > high)
• Array with duplicate values inside the range
• Negative numbers in the range
• Target values only at the first or last index of the array
• Integer.MIN_VALUE / Integer.MAX_VALUE used as range bounds

Additional Considerations

The algorithm runs in O(n + k) time, where n is arr.length and k is the range size high - low + 1; each array element and each range slot is visited at most once. Space usage is O(k) for the present array, which is separate from the input size.

Watch the range bounds when they sit near Integer.MIN_VALUE or Integer.MAX_VALUE: computing high - low + 1 can overflow a 32-bit int before it ever reaches new boolean[rangeSize]. If the range bounds are untrusted input, compute the size using long arithmetic first and validate it fits in memory before allocating.

Interview Follow-up Questions

Once the base solution is working, expect the interviewer to push further in these directions:

• What if the range is huge but the array is small, like low=0 and high=1,000,000,000? - avoid allocating a boolean array sized to the range; instead build a HashSet of only the array's values that fall inside the range, then check its size equals the range size.
• What if the array arrives as a stream of unknown length instead of a fixed array? - keep a HashSet seeded with every target value in the range, remove a value as soon as it is seen, and declare full coverage the moment the set becomes empty.
• What if you must solve it with O(1) extra space? - sort the array in place, then for each target value in the range run a binary search over the sorted array, trading the O(k) boolean array for O(n log n) time.
• What if you need to verify coverage for several disjoint ranges at once? - sort the ranges and the array once, then sweep both together so each range's coverage is checked in a single pass instead of restarting the scan per range.

Conclusion

Checking whether an array covers a range comes down to turning the range itself into a checklist and marking it off as you scan the array once. The same present[] and remaining pattern you practiced here extends naturally to streaming inputs, huge sparse ranges, and multi-range coverage checks, so it's worth keeping in your back pocket for interviews. You can learn more about array-based problems like this one in our Arrays category.