Welcome to Subscribe On Youtube

Question

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

 163. Missing Ranges

 Given a sorted integer array where the range of elements are [0, 99] inclusive, return its missing ranges.

 For example, given [0, 1, 3, 50, 75], lower = 0 and upper = 99,
 return [“2”, “4->49”, “51->74”, “76->99”]

 @tag-array

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

• Java
• C++
• Python

• 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());
          }
      }
  }
  

• // 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
  
  

All Problems

All Solutions