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

Traverse the nums array.

  • 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 is an interval [lower, num-1], otherwise just add a number

When there is an integer maximum value in the array, it will overflow when lower is updated to num+1, so make a judgment before updating.

  • If num is already the maximum value of an integer, just return the result res directly;
  • Otherwise, update lower and continue the loop. After the for loop exits, there may still be a missing interval at this time, that is, when lower is less than or equal to upper, the lower number or the [lower, upper] interval may be missing, and finally this interval will be added

Code

Java

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