LeetCode 163: Missing Ranges (Sentinel Boundary Scan)
LeetCode 163ArrayIntervalToday we solve LeetCode 163 - Missing Ranges.
Source: https://leetcode.com/problems/missing-ranges/
English
Problem Summary
Given a sorted unique integer array nums and inclusive bounds lower, upper, return all missing ranges inside [lower, upper].
Key Insight
Treat lower - 1 and upper + 1 as virtual sentinels. For each adjacent pair prev, curr, if curr - prev > 1, then the missing interval is [prev + 1, curr - 1].
Optimal Algorithm Steps
1) Initialize prev = lower - 1 (use long to avoid overflow).
2) Iterate index i from 0 to n (inclusive), where last curr = upper + 1.
3) If curr - prev > 1, format one missing range string.
4) Move prev = curr and continue.
Complexity Analysis
Time: O(n).
Space: O(1) extra (excluding output).
Common Pitfalls
- Forgetting boundary gaps before first element or after last element.
- Using int math and overflowing on lower - 1 or upper + 1.
- Wrong single-value formatting (must output "x", not "x->x").
- Not respecting sorted unique assumption when reusing the pattern elsewhere.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public List<String> findMissingRanges(int[] nums, int lower, int upper) {
List<String> ans = new ArrayList<>();
long prev = (long) lower - 1;
for (int i = 0; i <= nums.length; i++) {
long curr = (i == nums.length) ? (long) upper + 1 : nums[i];
if (curr - prev > 1) {
ans.add(format(prev + 1, curr - 1));
}
prev = curr;
}
return ans;
}
private String format(long l, long r) {
return l == r ? String.valueOf(l) : l + "->" + r;
}
}func findMissingRanges(nums []int, lower int, upper int) []string {
ans := []string{}
prev := int64(lower) - 1
for i := 0; i <= len(nums); i++ {
var curr int64
if i == len(nums) {
curr = int64(upper) + 1
} else {
curr = int64(nums[i])
}
if curr-prev > 1 {
ans = append(ans, formatRange(prev+1, curr-1))
}
prev = curr
}
return ans
}
func formatRange(l int64, r int64) string {
if l == r {
return fmt.Sprintf("%d", l)
}
return fmt.Sprintf("%d->%d", l, r)
}class Solution {
public:
vector<string> findMissingRanges(vector<int>& nums, int lower, int upper) {
vector<string> ans;
long long prev = (long long)lower - 1;
for (int i = 0; i <= (int)nums.size(); ++i) {
long long curr = (i == (int)nums.size()) ? (long long)upper + 1 : nums[i];
if (curr - prev > 1) {
ans.push_back(format(prev + 1, curr - 1));
}
prev = curr;
}
return ans;
}
private:
string format(long long l, long long r) {
if (l == r) return to_string(l);
return to_string(l) + "->" + to_string(r);
}
};class Solution:
def findMissingRanges(self, nums: List[int], lower: int, upper: int) -> List[str]:
ans: List[str] = []
prev = lower - 1
for i in range(len(nums) + 1):
curr = upper + 1 if i == len(nums) else nums[i]
if curr - prev > 1:
ans.append(self._format(prev + 1, curr - 1))
prev = curr
return ans
def _format(self, l: int, r: int) -> str:
return str(l) if l == r else f"{l}->{r}"/**
* @param {number[]} nums
* @param {number} lower
* @param {number} upper
* @return {string[]}
*/
var findMissingRanges = function(nums, lower, upper) {
const ans = [];
let prev = lower - 1;
for (let i = 0; i <= nums.length; i++) {
const curr = (i === nums.length) ? upper + 1 : nums[i];
if (curr - prev > 1) {
ans.push(format(prev + 1, curr - 1));
}
prev = curr;
}
return ans;
};
function format(l, r) {
return l === r ? String(l) : `${l}->${r}`;
}中文
题目概述
给定有序且互不重复的整数数组 nums，以及区间边界 lower、upper，返回闭区间 [lower, upper] 内所有缺失区间。
核心思路
把 lower - 1 和 upper + 1 当作两侧哨兵。对相邻的 prev 和 curr，若 curr - prev > 1，则缺失区间就是 [prev + 1, curr - 1]。
最优算法步骤
1）初始化 prev = lower - 1（建议用 long 防溢出）。
2）下标从 0 遍历到 n（含），最后一次把 curr 视为 upper + 1。
3）若 curr - prev > 1，说明中间有缺口，格式化后加入答案。
4）更新 prev = curr，继续扫描。
复杂度分析
时间复杂度：O(n)。
空间复杂度：O(1) 额外空间（不计输出）。
常见陷阱
- 漏掉数组前后的边界缺口。
- 直接用 int 做 lower - 1/upper + 1 可能溢出。
- 单点区间格式错误；单个数字应输出 "x"，不是 "x->x"。
- 把该模板直接套到“非有序/有重复”输入而不先预处理。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public List<String> findMissingRanges(int[] nums, int lower, int upper) {
List<String> ans = new ArrayList<>();
long prev = (long) lower - 1;
for (int i = 0; i <= nums.length; i++) {
long curr = (i == nums.length) ? (long) upper + 1 : nums[i];
if (curr - prev > 1) {
ans.add(format(prev + 1, curr - 1));
}
prev = curr;
}
return ans;
}
private String format(long l, long r) {
return l == r ? String.valueOf(l) : l + "->" + r;
}
}func findMissingRanges(nums []int, lower int, upper int) []string {
ans := []string{}
prev := int64(lower) - 1
for i := 0; i <= len(nums); i++ {
var curr int64
if i == len(nums) {
curr = int64(upper) + 1
} else {
curr = int64(nums[i])
}
if curr-prev > 1 {
ans = append(ans, formatRange(prev+1, curr-1))
}
prev = curr
}
return ans
}
func formatRange(l int64, r int64) string {
if l == r {
return fmt.Sprintf("%d", l)
}
return fmt.Sprintf("%d->%d", l, r)
}class Solution {
public:
vector<string> findMissingRanges(vector<int>& nums, int lower, int upper) {
vector<string> ans;
long long prev = (long long)lower - 1;
for (int i = 0; i <= (int)nums.size(); ++i) {
long long curr = (i == (int)nums.size()) ? (long long)upper + 1 : nums[i];
if (curr - prev > 1) {
ans.push_back(format(prev + 1, curr - 1));
}
prev = curr;
}
return ans;
}
private:
string format(long long l, long long r) {
if (l == r) return to_string(l);
return to_string(l) + "->" + to_string(r);
}
};class Solution:
def findMissingRanges(self, nums: List[int], lower: int, upper: int) -> List[str]:
ans: List[str] = []
prev = lower - 1
for i in range(len(nums) + 1):
curr = upper + 1 if i == len(nums) else nums[i]
if curr - prev > 1:
ans.append(self._format(prev + 1, curr - 1))
prev = curr
return ans
def _format(self, l: int, r: int) -> str:
return str(l) if l == r else f"{l}->{r}"/**
* @param {number[]} nums
* @param {number} lower
* @param {number} upper
* @return {string[]}
*/
var findMissingRanges = function(nums, lower, upper) {
const ans = [];
let prev = lower - 1;
for (let i = 0; i <= nums.length; i++) {
const curr = (i === nums.length) ? upper + 1 : nums[i];
if (curr - prev > 1) {
ans.push(format(prev + 1, curr - 1));
}
prev = curr;
}
return ans;
};
function format(l, r) {
return l === r ? String(l) : `${l}->${r}`;
}
Comments