/163. Find Missing Ranges in Sorted Array

163. Find Missing Ranges in Sorted Array

Easy
Arrays35.5% acceptance

Given a sorted list of distinct integers sorted_nums and two integers lower_bound and upper_bound, return a list of the smallest ranges that cover every missing number between lower_bound and upper_bound inclusive. Each range should be represented as a string: if the range contains only one number, use the number itself; otherwise, use the format start->end.

Example 1

Input: sorted_nums=[2, 4, 7], lower_bound=1, upper_bound=8

Output: [1, 3, 5->6, 8]

Explanation: Missing numbers are 1, 3, 5, 6, 8. Single numbers are represented as themselves, consecutive as ranges.

Example 2

Input: sorted_nums=[5], lower_bound=3, upper_bound=7

Output: [3->4, 6->7]

Explanation: Missing numbers are 3, 4, 6, 7.

Example 3

Input: sorted_nums=[], lower_bound=0, upper_bound=2

Output: [0->2]

Explanation: All numbers between 0 and 2 are missing.

Constraints

  • 1 <= len(sorted_nums) <= 100
  • -10^9 <= lower_bound <= upper_bound <= 10^9
  • All elements in sorted_nums are distinct and sorted in ascending order
  • lower_bound <= sorted_nums[0] (if sorted_nums is non-empty)
  • sorted_nums[-1] <= upper_bound (if sorted_nums is non-empty)
Python (current runtime)

Case 1

Input: sorted_nums=[10, 12, 15], lower_bound=9, upper_bound=16

Expected: ['9', '11', '13->14', '16']

Case 2

Input: sorted_nums=[1, 3, 5, 7], lower_bound=1, upper_bound=7

Expected: ['2', '4', '6']

Case 3

Input: sorted_nums=[-2, 0, 2], lower_bound=-3, upper_bound=3

Expected: ['-3', '-1', '1', '3']

Case 4

Input: sorted_nums=[100], lower_bound=99, upper_bound=101

Expected: ['99', '101']

Case 5

Input: sorted_nums=[], lower_bound=5, upper_bound=8

Expected: ['5->8']