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

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

One thought on “163. (Locked)Missing Ranges

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s