Write a function that takes a list of integers and outputs a list of pairs representing the consecutive ranges contained in the inputlist. Note: the input list is sorted.
arr1 = [1,3,4]
Output = [(1,1),(3,4)]
arr2 = [1,2,3,4,5]
Output = [(1,5)]
arr3 = [1,1,1,3,4,5,6,7,9]
Output = [(1,1), (3,7), (9,9)]
class Range {
int a;
int b;
public Range(int a, int b) {
this.a = a;
this.b = b;
}
@Override
public String toString() {
return "(" + a + ", " + b + ")";
}
}
public List<Range> getConsecutiveRanges(int[] arr) {
List<Range> ranges = new ArrayList<>();
Integer left = null, right = null;
int i = 0;
while (i < arr.length) {
if (left == null) {
left = arr[i];
right = arr[i];
i++;
} else if (arr[i] == right || arr[i] == right + 1) {
right = arr[i];
i++;
} else {
ranges.add(new Range(left, right));
left = null;
right = null;
}
}
if (left != null) {
ranges.add(new Range(left, right));
}
return ranges;
}If we can assume that the array is going to include unique values while remaining sorted, we can use the binary search logic as follows:
public List<Range> getConsecutiveRangesOptimized(int[] arr) {
List<Range> ranges = new ArrayList<>();
getConsecutiveRangesOptimized(arr, 0, arr.length - 1, ranges);
return ranges;
}
private void getConsecutiveRangesOptimized(int[] arr, int left, int right, List<Range> ranges) {
if (left > right) {
return;
}
if (arr[right] - arr[left] == right - left || left == right) {
if (ranges.isEmpty() || ranges.get(ranges.size() - 1).b + 1 < arr[left]) {
ranges.add(new Range(arr[left], arr[right]));
} else {
ranges.get(ranges.size() - 1).b = arr[right];
}
return;
}
int mid = (left + right) >>> 1;
getConsecutiveRangesOptimized(arr, left, mid, ranges);
getConsecutiveRangesOptimized(arr, mid + 1, right, ranges);
}Comments (13)