**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”]

Example Questions Candidate Might Ask:

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<string> findMissingRanges(array<int> vals, int start, int end) { vector<string> results; int prev = start - 1; for (int i = 0; i <= 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 > 2) { string val = to_string(prev + 1) + "->" + 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

Advertisements

[…] Missing Ranges […]

LikeLike