Description
Given a sorted integer array without duplicates, return the summary of its ranges.
Example 1:
Input: [0,1,2,4,5,7]
Output: ["0->2","4->5","7"]
Example 2:
Input: [0,2,3,4,6,8,9]
Output: ["0","2->4","6","8->9"]
Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.
Solution
Two-pointer, time O(n), space O(1)
class Solution {
public List<String> summaryRanges(int[] nums) {
List<String> ranges = new ArrayList<>();
if (nums == null || nums.length == 0) {
return ranges;
}
int rangeStart = 0;
int n = nums.length;
while (rangeStart < n) {
int rangeEnd = rangeStart;
while (rangeEnd < n - 1 && nums[rangeEnd + 1] - nums[rangeEnd] == 1) {
++rangeEnd;
}
if (rangeEnd > rangeStart) {
ranges.add(nums[rangeStart] + "->" + nums[rangeEnd]);
} else {
ranges.add(nums[rangeStart] + "");
}
rangeStart = rangeEnd + 1;
}
return ranges;
}
}
