Missing Ranges - Solution & Explanation

Problem Overview: You receive a sorted integer array nums and two bounds lower and upper. The task is to return every number range missing from the array within that inclusive interval. If a gap contains one number, output that number. If it contains multiple numbers, return the range in the format a->b.

Approach 1: Brute Force Range Check (O(R) time, O(1) space)

The most direct idea is to iterate through every integer between lower and upper and check whether it exists in the array. Convert the array into a set for constant‑time membership lookup, then walk through the full numeric interval and track consecutive missing numbers to form ranges. The complexity depends on the numeric span R = upper - lower, not the array size. This works but becomes inefficient when the bounds cover large ranges. Useful mainly for reasoning about the problem before optimizing.

Approach 2: Linear Scan with Previous Pointer (O(n) time, O(1) space)

The optimal approach relies on the fact that the array is already sorted. Track a variable prev representing the previous observed value. Initialize it to lower - 1. Iterate through the array and treat each element as the next boundary. If the difference between the current number and prev is greater than 1, a missing interval exists between them. Convert that gap into either a single number or a range string. Update prev after each step and perform a final check against upper after the loop. This scan only touches each element once, making it an O(n) solution with constant extra memory.

This method is essentially a gap detection problem on a sorted sequence. Because the array ordering guarantees monotonic growth, you never need extra data structures or binary searches. Just compare neighbors and emit ranges whenever a difference appears. The idea is closely related to interval processing patterns commonly used with arrays and boundary tracking problems.

Approach 3: Sentinel Boundary Technique (O(n) time, O(1) space)

A slight variation simplifies edge handling by conceptually adding two sentinel values: lower - 1 at the beginning and upper + 1 at the end. Iterate through the extended sequence and compute gaps between consecutive values. Every difference larger than one produces a missing range. This removes special cases for the first and last intervals and keeps the logic symmetric across the loop. The runtime remains O(n) with constant space.

Recommended for interviews: The linear scan with a previous pointer is what most interviewers expect. It demonstrates that you recognized the sorted property and solved the problem using a single pass. Mentioning the brute force approach first shows problem‑solving progression, but the O(n) gap detection solution reflects stronger algorithmic thinking. Problems like this commonly appear in discussions around array traversal and interval-style reasoning.