LeetCode - Missing Ranges
Problem description
Given a sorted integer array nums, where the range of elements are in the inclusive range [lower, upper], return its missing ranges.
Example:
1
2
Input: nums = [0, 1, 3, 50, 75], lower = 0 and upper = 99,
Output: ["2", "4->49", "51->74", "76->99"]
Analysis
Just use three steps to get the answer. lower and arr[0], arr[1] to arr[len-1]’s intervals. arr[len-1] and upper.
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
class Solution {
public List<String> findMissingRanges(int[] nums, int lower, int upper) {
List<String> result = new ArrayList<>();
if (nums == null || nums.length == 0){
result.add(formRange(lower,upper));
return result;
}
// 1st step
if (nums[0] > lower){
result.add(formRange(lower,nums[0]-1));
}
// 2nd step
for (int i = 0; i < nums.length-1; i++){
if (nums[i+1] != nums[i] && nums[i+1] > nums[i] +1) {
result.add(formRange(nums[i]+1, nums[i+1]-1));
}
}
// 3rd step
if (nums[nums.length-1] < upper){
result.add(formRange(nums[nums.length-1]+1, upper));
}
return result;
}
public String formRange(int low, int high){
return low == high ? String.valueOf(low) : (low + "->" + high);
}
}
What to improve
- analysis step by step.