163 Missing Ranges
Problem
Given a sorted integer array where the range of elements are in the inclusive range [lower, upper], return its missing ranges.
For example, given [0, 1, 3, 50, 75], lower = 0 and upper = 99, return [“2”, “4->49”, “51->74”, “76->99”].
Thoughts:
The first thought I had for this problem is to do in a recursive way. One thing need to deal with is about Integer overflow. Actually, I think it’s good to always keep in mind about Integer overflow when you are adding a Integer.
Because, when using a recursive solution, it uses stack to store the state of the function call. So we might need a iterative way which will save some time and be more efficient. In the second solution, it’s using a iterative way, but still we need to deal with the integer overflow case.
Solutions:
public class Solution {
public List<String> findMissingRanges(int[] nums, int lower, int upper) {
List<String> result = new LinkedList<String>();
if (nums.length == 0) {
findRange(result, lower, upper);
return result;
}
if (nums[0] != Integer.MIN_VALUE) {
findRange(result, lower, nums[0] - 1);
}
for (int i = 0; i < nums.length - 1; i ++) {
if (nums[i] == nums[i+1]) {
continue;
}
findRange(result, nums[i] + 1, nums[i+1] - 1);
}
if (nums[nums.length - 1] != Integer.MAX_VALUE) {
findRange(result, nums[nums.length - 1] + 1, upper);
}
return result;
}
private void findRange(List<String> result, int low, int up) {
if (low > up){
return;
}
if (low == up) {
result.add((low) + "");
return;
}
result.add(low + "->" + up);
}
}
Iterative:
public class Solution {
public List<String> findMissingRanges(int[] nums, int lower, int upper) {
List<String> result = new LinkedList<String>();
int left = 0, right = 0;
for (int i = -1; i < nums.length; i ++) {
if (i >= 0) {
left = nums[i] + 1;
if (left == Integer.MIN_VALUE) {
continue;
}
}
else {
left = lower;
}
if (i + 1 < nums.length) {
right = nums[i + 1] - 1;
if (right == Integer.MAX_VALUE) {
continue;
}
}
else{
right = upper;
}
if (left > right) {
continue;
}
if (left == right) {
result.add(left + "");
continue;
}
result.add(left + "->" + right);
}
return result;
}
}
class Solution {
public List<String> findMissingRanges(int[] nums, int lower, int upper) {
List<String> res = new LinkedList<String>();
int low = lower;
int up = upper;
boolean overflow = false;
for (int i = 0; i < nums.length; i ++) {
if (low < nums[i]) {
res.add(getRange(low, nums[i] - 1));
}
low = nums[i] + 1;
if (low == Integer.MIN_VALUE) {
overflow = true;
break;
}
}
if (low <= up && overflow == false) {
res.add(getRange(low, up));
}
return res;
}
private String getRange(int a, int b) {
if (a == b) {
return a+"";
}
else {
return a + "->" + b;
}
}
}