### Leetcode: 163. Missing Ranges

Blog Post: 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)
missingRanges.push_back(vector<int>{lower, nums - 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!