# 163. (Locked)Missing Ranges

Difficulty: Medium

Frequency: N/A

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], return [“2”, “4->49”, “51->74”, “76->99”]

Q: What if the given array is empty?
A: Then you should return [“0->99”] as those ranges are missing.

Q: What if the given array contains all elements from the ranges? A: Return an empty list, which means no range is missing.

My solution:
Data structure:
array, list
Steps:
1. For each two adjacent ints in the array(including start – 1 and end + 1), calculate the range
2. how to calculate the range between a and b
2.1 If b – a == 1, nothing
2.2 If b – a == 2, return (b + a) /2
2.3 If b – a > 2, return (a + 1)->(b – 1)
Complexity:
Runtime: O(n)
Space: O(n)
Test cases:
[0, 1, 3, 50, 75]
Corner cases:
[]
[0, 1, …, 99]
Code:
```
class Solution {
public:
vector&lt;string&gt; findMissingRanges(array&lt;int&gt; vals, int start, int end) {
vector&lt;string&gt; results;
int prev = start - 1;
for (int i = 0; i &lt;= vals.size(); i++) {
// handle the last element(end)
int curr = (i == vals.size()) ? end + 1 : vals[i];
if (curr - prev == 2) {
results.push_back(to_string(prev + 1));
} else if (curr - prev &gt; 2) {
string val = to_string(prev + 1) + &quot;-&gt;&quot; + to_string(curr - 1);
results.push_back(val);
}
prev = curr;
}
return results;
}
}
```

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:
1. It is very import to unify the problem, then do not need to handle special case
2. Need to know handy c++ functions

## One thought on “163. (Locked)Missing Ranges”

1. […]  Missing Ranges […]

Like