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: []

---

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 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.

---

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.