Leetcode: 163. Missing Ranges

Missing Ranges

Today, let's explore an interesting problem related to arrays: finding missing ranges within a given range. We will be solving this problem using a simple and efficient algorithm. Let's dive right in!

Problem Statement

Given a sorted integer array nums, and two integers lower and upper, our task is to find and return the missing ranges in the range [lower, upper] that are not covered by the elements in the array. The output should be a 2D vector, where each row represents a missing range and contains two integers start and end.

Approach

We can solve this problem by iterating through the array nums and identifying the missing ranges. We will traverse the array and check for the differences between consecutive elements to identify the gaps.

Let's analyze the complexity of our solution:

• Time Complexity: The algorithm traverses the array nums once, which takes O(n) time, where n is the number of elements in the array. Hence, the overall time complexity is O(n).
• Space Complexity: We use a 2D vector to store the missing ranges. In the worst case, there could be O(n) missing ranges, each requiring two integers to represent the start and end points. Thus, the space complexity is O(n).

Code Example

Below is the C++ code implementation of the solution:

class Solution {
public:
    vector<vector<int>> findMissingRanges(vector<int>& nums, int lower, int upper) {
        int n = nums.size();
        vector<vector<int>> missingRanges;
        if (n == 0)
        {
            missingRanges.push_back(vector<int>{lower, upper});
            return missingRanges;
        }

        if (lower < nums[0])
            missingRanges.push_back(vector<int>{lower, nums[0] - 1});

        for (int i = 0; i < n - 1; i++) {
            if (nums[i + 1] - nums[i] <= 1) {
                continue;
            }
            missingRanges.push_back(vector<int>{nums[i] + 1, nums[i + 1] - 1});
        }

        if (upper > nums[n - 1]) {
            missingRanges.push_back(vector<int>{nums[n - 1] + 1, upper});
        }

        return missingRanges;
    }
};

With this implementation, you can now easily find the missing ranges within the given range using the provided function findMissingRanges().

Example

Let's take an example to understand the function's usage:

// Input:
vector<int> nums = {3, 5, 10};
int lower = 2, upper = 15;

// Output:
vector<vector<int>> result = findMissingRanges(nums, lower, upper);
// The output should be: {{2, 2}, {4, 4}, {6, 9}, {11, 15}}

By using the provided function with the given input, you can find the missing ranges and obtain the output as mentioned in the example above.

I hope you found this blog post helpful in understanding the Missing Ranges problem and its solution. Happy coding!