Skip to content

163. Missing Ranges 👎

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
 public:
  vector<string> findMissingRanges(vector<int>& nums, int lower, int upper) {
    if (nums.empty())
      return {getRange(lower, upper)};

    vector<string> ans;

    if (nums.front() > lower)
      ans.push_back(getRange(lower, nums.front() - 1));

    for (int i = 1; i < nums.size(); ++i)
      if (nums[i] > nums[i - 1] + 1)
        ans.push_back(getRange(nums[i - 1] + 1, nums[i] - 1));

    if (nums.back() < upper)
      ans.push_back(getRange(nums.back() + 1, upper));

    return ans;
  }

 private:
  string getRange(int lo, int hi) {
    if (lo == hi)
      return to_string(lo);
    return to_string(lo) + "->" + to_string(hi);
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
  public List<String> findMissingRanges(int[] nums, int lower, int upper) {
    if (nums.length == 0)
      return new ArrayList<>(Arrays.asList(getRange(lower, upper)));

    List<String> ans = new ArrayList<>();

    if (nums[0] > lower)
      ans.add(getRange(lower, nums[0] - 1));

    for (int i = 1; i < nums.length; ++i)
      if (nums[i] > nums[i - 1] + 1)
        ans.add(getRange(nums[i - 1] + 1, nums[i] - 1));

    if (nums[nums.length - 1] < upper)
      ans.add(getRange(nums[nums.length - 1] + 1, upper));

    return ans;
  }

  private String getRange(int lo, int hi) {
    if (lo == hi)
      return String.valueOf(lo);
    return lo + "->" + hi;
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
  def findMissingRanges(self, nums: List[int], lower: int, upper: int) -> List[str]:
    def getRange(lo: int, hi: int) -> str:
      if lo == hi:
        return str(lo)
      return str(lo) + '->' + str(hi)

    if not nums:
      return [getRange(lower, upper)]

    ans = []

    if nums[0] > lower:
      ans.append(getRange(lower, nums[0] - 1))

    for prev, curr in zip(nums, nums[1:]):
      if curr > prev + 1:
        ans.append(getRange(prev + 1, curr - 1))

    if nums[-1] < upper:
      ans.append(getRange(nums[-1] + 1, upper))

    return ans