Leetcode 163. Missing Ranges

Problem Explanation

The task given is to find the missing range of numbers within a sorted integer array. We have given a lower and upper limit and our task is to find the range of missing numbers between lower and upper.

Let's walk through the example. We are given the integer array nums=[0, 1, 3, 50, 75] where lower limit=0 and upper limit=99. The missing numbers are: single number 2, a range 4 to 49, a range 51 to 74 and a range 76 to 99. In the format of missing ranges, the output is: ["2", "4->49", "51->74", "76->99"]

Approach

To solve this problem, we need to handle some special cases first. If the integer array is empty, then the entire range from lower to upper is missing, so we return that complete range.

We compare the first element of array (nums[0]) with lower limit. If the first element is greater than the lower limit, there are missing elements before the first number. We push the range from the lower to nums[0]-1 to our result array (as nums[0] is present in the array, we -1 to exclude that number).

Next step is to iterate through each element of the array and compare it with the previous element. If the current element is greater than the previous element + 1 (again, +1 to exclude the previous number which is in the list), we have missing numbers.

Finally, we compare the last element of array with the upper limit. If the last element is less than the upper limit, there are missing numbers after the last number. We push the range from nums.back()+1 to upper to our result array.

After the loop ends, we will have all the missing ranges pushed into the result vector.

Python Solution

1
2python
3class Solution:
4    def findMissingRanges(self, nums: List[int], lower: int, upper: int) -> List[str]:
5        result = []
6        nums.append(upper+1)
7        pre = lower - 1
8        for num in nums:
9            if (pre + 1 <= num - 1):
10                result.append(self.formatRange(pre + 1, num - 1))
11            pre = num
12        return result
13            
14    def formatRange(self, lower: int, upper: int) -> str:
15        if lower == upper:
16            return str(lower)
17        else:
18            return str(lower) + "->" + str(upper)

Java Solution

1
2java
3class Solution {
4    public List<String> findMissingRanges(int[] nums, int lower, int upper) {
5        List<String> res = new ArrayList<>();
6        if (nums == null || nums.length == 0) {
7            res.add(formRange(lower, upper));
8            return res;
9        }
10        if (lower < nums[0]) {
11            res.add(formRange(lower, nums[0] - 1));
12        }
13        for (int i = 1; i < nums.length; i++) {
14            if (nums[i] != nums[i - 1] && nums[i] > nums[i - 1] + 1) {
15                res.add(formRange(nums[i - 1] + 1, nums[i] - 1));
16            }
17        }
18        if (nums[nums.length - 1] < upper) {
19            res.add(formRange(nums[nums.length - 1] + 1, upper));
20        }
21        return res;
22    }
23    private String formRange(int low, int high) {
24        return low == high ? String.valueOf(low) : (low + "->" + high);
25    }
26}

JavaScript Solution

1
2javascript
3const findMissingRanges = function(nums, lower, upper) {
4    let next = lower;
5    let i = 0, res = [];
6  
7    while( next <= upper ) {
8        if(i < nums.length && nums[i] < next ) i++;
9        else if(i < nums.length && nums[i] == next) { i++; next++ }
10        else {
11                res.push(insertRange(next, getEndPos(upper, nums[i])));
12                if(i >= nums.length ) break;
13                next = nums[i] + 1;
14        }
15    }
16    return res;  
17}
18
19const getEndPos = function(pos1, pos2){
20    return (pos2 != null) ? Math.min(pos1, pos2 - 1) : pos1;
21}
22
23const insertRange = function(begin, end) {
24    return (begin==end) ? begin.toString() : begin + "->" + end
25}

C++ Solution

1
2cpp
3class Solution {
4public:
5    vector<string> findMissingRanges(vector<int>& nums, int lower, int upper) {
6        vector<string> result;
7        long start = lower;
8        for (auto& num : nums) {
9            if (num < start) continue;
10            if (num == start) { start++; continue; }
11            result.push_back(to_string(start) + (num - 1 > start ? "->" + to_string(num - 1) : ""));
12            start = (long)num + 1;
13        }
14        if (start <= upper) result.push_back(to_string(start) + (upper > start ? "->" + to_string(upper) : ""));
15        return result;
16    }
17};

C# Solution

1
2csharp
3public class Solution {
4    public IList<string> FindMissingRanges(int[] nums, int lower, int upper) {
5        List<string> res = new List<string>();
6        long next = lower;
7        foreach (int num in nums) {
8            if (next < num) 
9                res.Add(GetRange(next, num-1));
10            if (next != ulong.MaxValue) 
11                next = (long)num + 1;
12        }
13        if (next <= upper) 
14            res.Add(GetRange(next, upper));
15        
16        return res;
17    }
18    
19    public string GetRange(long low, long high) {
20        return low == high ? $"{low}" : $"{low}->{high}";
21    }
22}

The above solutions will help you solve this problem using different programming languages: Python, Java, JavaScript, C++, and C#. It is vital to note that all these solutions work based on the same concept, as explained in the "approach" section of this article.

They all follow a designed pattern of getting a range between two numbers, checking the differences between them while setting conditionals to handle edge cases of numbers appearing subsequently in the order, and concatenating the ranges where there are missing values.

To summarize the steps, we start from the lower limit and compare its value with numbers in the given array based on its order. If there are numbers missing, we record the range in which they are missing. If a number exists, we move to the next number and continue the process until we've covered up to the upper limit.

Finally, the solutions are elegant in that they effectively handle all edge cases while maintaining a low time complexity, making them efficient in solving the given problem of finding missing ranges.

If you wish to optimize the function in any way, you would explore method improvements that maintain the same concept but are executed with more efficient time and space complexity. However, remember that an essential part of designing a solution is ensuring readability and understanding of your code— sometimes, this is vital over slightly more efficient performance. Always aim for simplicity and readability first.


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫