Question

Formatted question description: https://leetcode.ca/all/163.html

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]]
Explanation: The ranges are:
[2,2]
[4,49]
[51,74]
[76,99]

Example 2:

Input: nums = [-1], lower = -1, upper = -1
Output: []
Explanation: There are no missing ranges since there are no missing numbers.

Constraints:

-10⁹ <= lower <= upper <= 10⁹
0 <= nums.length <= 100
lower <= nums[i] <= upper
All the values of nums are unique.

Algorithm

To find the missing intervals in an array nums, we can follow the below approach:

Traverse the nums array and compare each number with the lower bound of the interval we are looking for.
If the current number num is greater than lower, it means that there is a missing interval at this time, and at least one lower number is missing.
If num-1 is greater than lower, it means that the missing interval is [lower, num-1], so we add this missing interval to the result.
If num-1 is not greater than lower, it means that there is only one missing number, so we add that to the result.
When there is an integer maximum value in the array, updating lower to num+1 will cause an overflow. Therefore, before updating, we need to check if num is already the maximum value of an integer. If it is, we return the result directly without updating lower.
After the for loop exits, there may still be a missing interval, that is, when lower is less than or equal to upper, the lower number or the [lower, upper] interval may be missing, and we add this interval to the result.

Finally, we return the list of missing intervals as the result.

Code

import java.util.ArrayList;
import java.util.List;

public class Missing_Ranges {

    public static void main(String[] args) {
        Missing_Ranges out = new Missing_Ranges();
        Solution s = out.new Solution();

        System.out.println(s.findMissingRanges(new int[]{0, 1, 3, 50, 75}, 0, 99));
        System.out.println(s.findMissingRanges(new int[]{0, 1, 3, 50, 75}, -100, 50));
        System.out.println(s.findMissingRanges(new int[]{0, 1, 3, 50, 75}, 49, 200));
    }

    public class Solution {
        public List<String> findMissingRanges(int[] nums, int lower, int upper) {
            List<String> result = new ArrayList<String>();
            if (nums == null || nums.length == 0) {
                outputToResult(lower, upper, result);
                return result;
            }

            // leading missing range
            if (nums[0] - lower > 0) {
                outputToResult(lower, nums[0] - 1, result);
            }

            for (int i = 1; i < nums.length; i++) {
                if (nums[i] - nums[i - 1] > 1) { // @note: nice catch
                    outputToResult(nums[i - 1] + 1, nums[i] - 1, result);
                }
            }

            // trailing missage ranges
            if (upper - nums[nums.length - 1] > 0) {
                outputToResult(nums[nums.length - 1] + 1, upper, result);
            }

            return result;
        }

        private void outputToResult(int start, int end, List<String> result) {
            StringBuffer sb = new StringBuffer();
            if (start == end) {
                sb.append(start);
            } else {
                sb.append(start + "->" + end);
            }

            result.add(sb.toString());
        }
    }
}

############

class Solution {
    public List<String> findMissingRanges(int[] nums, int lower, int upper) {
        int n = nums.length;
        List<String> ans = new ArrayList<>();
        if (n == 0) {
            ans.add(f(lower, upper));
            return ans;
        }
        if (nums[0] > lower) {
            ans.add(f(lower, nums[0] - 1));
        }
        for (int i = 1; i < n; ++i) {
            int a = nums[i - 1], b = nums[i];
            if (b - a > 1) {
                ans.add(f(a + 1, b - 1));
            }
        }
        if (nums[n - 1] < upper) {
            ans.add(f(nums[n - 1] + 1, upper));
        }
        return ans;
    }

    private String f(int a, int b) {
        return a == b ? a + "" : a + "->" + b;
    }
}

// OJ: https://leetcode.com/problems/missing-ranges/
// Time: O(N)
// Space: O(1)
class Solution {
    string formatRange(int lower, int upper) {
        if (lower == upper) return to_string(lower);
        return to_string(lower) + "->" + to_string(upper);
    }
public:
    vector<string> findMissingRanges(vector<int>& A, int lower, int upper) {
        vector<string> ans;
        int i = lower, j = 0, N = A.size();
        while (j < N) {
            if (i == A[j]) {
                ++i;
                ++j;
            } else {
                int first = i, last = A[j] - 1;
                ans.push_back(formatRange(first, last));
                i = A[j++] + 1;
            }
        }
        if (i <= upper) ans.push_back(formatRange(i, upper));
        return ans;
    }
};

class Solution:
    def findMissingRanges(self, nums: List[int], lower: int, upper: int) -> List[str]:
        def f(a, b):
            return str(a) if a == b else f'{a}->{b}'

        n = len(nums)
        if n == 0:
            return [f(lower, upper)]
        ans = []
        if nums[0] > lower:
            ans.append(f(lower, nums[0] - 1))
        for a, b in pairwise(nums):
            if b - a > 1:
                ans.append(f(a + 1, b - 1))
        if nums[-1] < upper:
            ans.append(f(nums[-1] + 1, upper))
        return ans

############

class Solution(object):
  def findMissingRanges(self, nums, lower, upper):
    """
    :type nums: List[int]
    :type lower: int
    :type upper: int
    :rtype: List[str]
    """
    ans = []
    nums = [lower - 1] + nums + [upper + 1]
    for i in range(0, len(nums) - 1):
      if nums[i] + 2 == nums[i + 1]:
        ans.append(str(nums[i] + 1))
      if nums[i + 1] > nums[i] + 2:
        ans.append(str(nums[i] + 1) + "->" + str(nums[i + 1] - 1))
    return ans

func findMissingRanges(nums []int, lower int, upper int) (ans []string) {
	f := func(a, b int) string {
		if a == b {
			return strconv.Itoa(a)
		}
		return strconv.Itoa(a) + "->" + strconv.Itoa(b)
	}
	n := len(nums)
	if n == 0 {
		ans = append(ans, f(lower, upper))
		return
	}
	if nums[0] > lower {
		ans = append(ans, f(lower, nums[0]-1))
	}
	for i := 1; i < n; i++ {
		a, b := nums[i-1], nums[i]
		if b-a > 1 {
			ans = append(ans, f(a+1, b-1))
		}
	}
	if nums[n-1] < upper {
		ans = append(ans, f(nums[n-1]+1, upper))
	}
	return
}

163 - Missing Ranges

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions