Given a sorted integer array where the range of elements are [lower, upper] inclusive, return its missing ranges.
For example, given
Understand the problem:[0, 1, 3, 50, 75]
, lower = 0 and upper = 99, return ["2", "4->49", "51->74", "76->99"].
The problem itself is not hard at all. The key is to handle several corner cases. e.g.
-- If the array is empty, the missing ranges should be from lower to upper, inclusive.
-- For the leading missing range, e.g. -2 , [-1], -1. The output should be "-2". Note that the lower bound is inclusive.
-- For the trailing missing range, e.g. -2, [-2], 1, the output should be "-1->1". The upper bound is inclusive as well.
Code (Java):
public class Solution { public List<String> findMissingRanges(int[] nums, int lower, int upper) { List<String> result = new ArrayList<String>(); if (nums == null || nums.length == 0) { outputToResult(lower, upper, result); return result; } // leading missing range if (nums[0] - lower > 0) { outputToResult(lower, nums[0] - 1, result); } for (int i = 1; i < nums.length; i++) { if (nums[i] - nums[i - 1] > 1) { outputToResult(nums[i - 1] + 1, nums[i] - 1, result); } } // trailing missage ranges if (upper - nums[nums.length - 1] > 0) { outputToResult(nums[nums.length - 1] + 1, upper, result); } return result; } private void outputToResult(int start, int end, List<String> result) { StringBuffer sb = new StringBuffer(); if (start == end) { sb.append(start); } else { sb.append(start + "->" + end); } result.add(sb.toString()); } }
[-2147483648,2147483647]
ReplyDelete-2147483648
2147483647
Fails for this case