### 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!

## Comments

## Post a Comment