Missing Ranges - Solution & Explanation

Problem Overview: You are given a sorted integer array nums and two boundaries lower and upper. The task is to report every missing range of numbers between these bounds that does not appear in the array. Each gap between consecutive values represents a missing range.

Approach 1: Brute Force Range Check (O((upper-lower)) time, O(1) space)

The most direct idea is to iterate through every integer from lower to upper and check whether it appears in the array. You maintain a pointer in nums and compare each candidate number against it. When a number is missing, start building a range until a present number appears again. This works conceptually but becomes inefficient when the numeric interval is large because the algorithm examines every value even if the array itself is small.

Approach 2: Simulation with Gap Detection (O(n) time, O(1) space)

The optimal solution scans the sorted array once and detects gaps between adjacent numbers. Track a variable prev representing the last observed value, initialized to lower - 1. For each number curr in nums, check if curr - prev > 1. When this condition holds, the interval [prev + 1, curr - 1] is a missing range. Append that range to the result list, formatting it as a single number or a range string depending on its size.

After processing the array, run one final check using a sentinel value upper + 1 to capture the last possible gap. Because the array is already sorted, every missing segment is discovered by comparing neighboring values rather than scanning the entire numeric interval. The algorithm performs a single pass over the array and stores only the resulting ranges.

This method relies purely on sequential iteration and boundary comparisons, which makes it a classic array traversal pattern. The gap-detection logic is similar to problems that analyze consecutive elements or use lightweight two-pointer style iteration across ordered data. Understanding how to detect intervals between values is useful in range-based problems and interval processing patterns.

Recommended for interviews: Interviewers expect the linear scan simulation approach. The brute force method demonstrates basic understanding of the problem but fails when the range between lower and upper becomes large. The gap-detection approach shows that you recognize the sorted property of the array and convert the problem into comparing consecutive elements, achieving O(n) time with constant space.