LeetCode [163] Missing Ranges

163. Missing Ranges

Medium

Given a sorted integer array nums, where the range of elements are in the inclusive range [lower, upper], return its missing ranges.

Example:

Input: nums = [0, 1, 3, 50, 75], lower = 0 and upper = 99,
Output: ["2", "4->49", "51->74", "76->99"]

========
* keep update lower bound "l"
* use "long long" to resolve overflow
========

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

typedef long long ll; class Solution { public: void updateIntv(ll l, ll r, vector<string>& ret) { if(l==r) ret.push_back(to_string(l)); if(l<r) ret.push_back(to_string(l)+"->"+to_string(r)); } vector<string> findMissingRanges(vector<int>& nums, int lower, int upper) { vector<string> ret; int n = nums.size(), i = 0; ll l = lower; while(i<n){ ll v = nums[i++]; updateIntv(l, v-1, ret); l = v+1; } updateIntv(l, upper, ret); return ret; } };

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

class Solution { public List<String> findMissingRanges(int[] nums, int lower, int upper) { List<String> list = new ArrayList<>(); int left = lower; for(int i : nums){ int right = i-1; if(right>left){ list.add(left + "->" + right); }else if(right==left){ list.add(String.valueOf(left)); } left = i+1; } if(left<=upper){ if(left==upper) list.add(String.valueOf(left)); else list.add(left + "->" + upper); } return list; } }