Missing Ranges

Problem

You are given a sorted array of distinct integers nums and two integers lower and upper with lower <= upper. Every element of nums lies within [lower, upper]. A number in [lower, upper] is missing if it does not appear in nums. Return the missing numbers grouped into maximal contiguous ranges, as a list of [start, end] pairs in increasing order. Each pair covers the inclusive range of missing values from start to end.

• The array may be empty and has at most a few hundred elements.
• lower and upper can be anywhere in the signed 32-bit range, so the interval may span billions of values.
• Elements are strictly increasing and all lie inside [lower, upper].

Examples

• nums = [12, 14, 15, 30], lower = 10, upper = 40 → [[10, 11], [13, 13], [16, 29], [31, 40]]. A head gap before 12, gaps between present values, and a tail gap up to 40.
• nums = [], lower = 7, upper = 7 → [[7, 7]]. Nothing is present, so the single value 7 is missing.
• nums = [5], lower = 5, upper = 5 → []. The only value in range is present.

Hints

1. A gap exists between two consecutive present values a and b exactly when b - a > 1; the gap is [a + 1, b - 1].
2. The first gap may start at lower and the last may end at upper. Can you make those look like ordinary gaps?
3. Treat lower - 1 and upper + 1 as virtual sentinels on each side of the array, then apply the gap rule uniformly to every adjacent pair.