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):
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 29 30 31 32 33 34 35 36 37 38 | 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