Missing Ranges: Array Sweeping

[!NOTE] This module explores the core principles of Missing Ranges: Array Sweeping, deriving solutions from first principles and hardware constraints to build world-class, production-ready expertise.

1. Problem Definition

You are given an inclusive range [lower, upper] and a sorted unique integer array nums, where all elements are within the inclusive range.

A number x is considered missing if x is in the range [lower, upper] and x is not in nums.

Return the shortest sorted list of ranges that exactly covers all the missing numbers. That is, no element of nums is included in any of the ranges, and each missing number is covered by one of the ranges.

Example 1:

Input: nums = [0,1,3,50,75], lower = 0, upper = 99
Output: [[2,2],[4,49],[51,74],[76,99]]

Example 2:

Input: nums = [-1], lower = -1, upper = -1
Output: []

Edge Cases & Clarifying Questions

  • What if the array is empty?
    • The entire range [lower, upper] is missing.
  • What if lower == upper?
    • If the number is in the array, return empty. Otherwise, return [[lower, upper]].
  • Can there be duplicates in the array?
    • The problem states it’s a “sorted unique integer array”.
  • What if the array covers the entire range perfectly?
    • Return an empty list.

2. Interactive Analysis

Click “Next Step” to see how the lower pointer sweeps across the array, identifying gaps between the expected value and the actual array elements.

Variables:
lower = 0
upper = 99
nums:

Output (Missing Ranges)

Click 'Next Step' to begin the sweep.

3. Intuition (The “Genesis”)

Brute Force Approach

The naive approach is to iterate from lower to upper one by one, checking if each number exists in nums. Since nums is sorted, we could use Binary Search or a Hash Set to check existence. If we use a Hash Set, time is O(N) to build, then O(upper - lower) to check. If upper - lower is billions, this results in Time Limit Exceeded (TLE) and massive space overhead.

Optimized Approach: Array Sweeping

Instead of checking every number in the range, we iterate through the given numbers and calculate the gaps between them. We maintain a pointer to the “expected next number” (starting at lower). For each number x in the array:

  1. If our expected number is less than x, we’ve found a gap [expected, x - 1].
  2. Update our expected number to x + 1. Finally, after the loop, if our expected number is still <= upper, we add the final gap [expected, upper].

Intuition Through Analogy

Imagine you are a security guard walking along a fence line from point A (lower) to point B (upper). You have a list of checkpoints (nums) where a camera is actively monitoring the fence. Your job is to report the exact stretches of the fence that are unmonitored.

The Strategy: You start walking from the very beginning (lower).

  1. You look at the first camera’s location. If the camera is ahead of where you are standing, the stretch from your feet to just before the camera is a blind spot (a missing range).
  2. You then teleport to just after the camera. That becomes your new starting point.
  3. You repeat this for every camera.
  4. Finally, after passing the last camera, you check if there is still unmonitored fence before the end (upper). If so, that final stretch is also a blind spot.

By keeping track of an expected_next_number (your current location on the fence), you can seamlessly sweep across the entire problem space in a single, elegant pass.

Common Pitfalls

  • Integer Overflow: If nums[i] is Integer.MAX_VALUE, nums[i] + 1 overflows. We should carefully handle boundaries or use larger data types if inputs can hit limits.
  • Forgetting the Final Boundary: Often candidates finish the loop but forget to check the gap between the last element of nums and upper.

4. Solutions

Java
Go
class Solution {
  public List<List<Integer>> findMissingRanges(int[] nums, int lower, int upper) {
    List<List<Integer>> ans = new ArrayList<>();

    for (int i = 0; i < nums.length; i++) {
      // Gap identified between the 'expected' lower bound and actual number
      if (lower < nums[i]) {
        ans.add(Arrays.asList(lower, nums[i] - 1));
      }
      // Advance the expected lower bound to the next possible integer
      lower = nums[i] + 1;
    }

    // Post-processing: Check the boundary gap after the loop finishes
    if (lower <= upper) {
      ans.add(Arrays.asList(lower, upper));
    }

    return ans;
  }
}

func findMissingRanges(nums []int, lower int, upper int) [][]int {
  var ans [][]int

  for _, num := range nums {
    if lower < num {
      ans = append(ans, []int{lower, num - 1})
    }
    lower = num + 1
  }

  if lower <= upper {
    ans = append(ans, []int{lower, upper})
  }

  return ans
}

5. Complexity Analysis

Strategy Time Space Notes
Array Sweeping O(N) O(1) Linear scan, constant auxiliary space.

Hardware Reality

  • Contiguous Memory: Arrays are stored as contiguous blocks of memory.
  • Hardware Prefetching: When the CPU reads nums[0], it automatically loads nums[1], nums[2], etc., into the L1/L2 Cache because it detects a predictable, linear access pattern.
  • Branch Prediction: The if (lower < nums[i]) branch is highly predictable.

6. Real World Patterns

  • IP Address Whitelisting/Blacklisting: Given a range of allowed IP addresses and an array of explicitly blocked IP addresses, calculating the contiguous blocks of allowed IPs.
  • Calendar Booking Systems: Finding available time slots. [0, 24] hours represents the day, and nums represents busy blocks (e.g. meetings). Our algorithm quickly extracts the free (unbooked) time slots.