Problem Statement:-
You are given a sorted unique integer array nums.
A range [a,b] is the set of all integers from a to b (inclusive).
Return the smallest sorted list of ranges that cover all the numbers in the array exactly. That is, each element of nums is covered by exactly one of the ranges, and there is no integer x such that x is in one of the ranges but not in nums.
Each range [a,b] in the list should be output as:
"a->b"ifa != b"a"ifa == b
Link: https://leetcode.com/problems/summary-ranges/description/
Problem Explanation with examples:-
Example 1
Input: nums = [0,1,2,4,5,7]
Output: ["0->2","4->5","7"]
Explanation: The ranges are:
[0,2] --> "0->2"
[4,5] --> "4->5"
[7,7] --> "7"
Example 2
Input: nums = [0,2,3,4,6,8,9]
Output: ["0","2->4","6","8->9"]
Explanation: The ranges are:
[0,0] --> "0"
[2,4] --> "2->4"
[6,6] --> "6"
[8,9] --> "8->9"
Constraints
0 <= nums.length <= 20-2<sup>31</sup> <= nums[i] <= 2<sup>31</sup> - 1All the values of
numsare unique.numsis sorted in ascending order.
Intuition:-
Append a number that is not in the array to the end of the array to account for the last range comparison.
If the difference between the current number and the previous number is not 1, then we have reached the end of a range. Append the range to the answer array and reset the range string.If the difference between the current number and the previous number is 1, then we are still in the same range. Update the previous number and continue.
Solution:-
Initialize an empty array to store the answer.
Initialize a string to store the current range.
If the array is empty, return the answer array.
If the last number in the array is not -2 or 0, then append -1 to the array. Else, append 2^31 to the array.
Initialize a variable to store the previous number. Set it to the first number in the array.
Iterate over the array from the second number to the last number. If the difference between the current number and the previous number is not 1, then we have reached the end of a range. If integer value of the range string is not equal to the previous number, then append the previous number to the range string. Append the range string to the answer array. Reset the range string to the current number. Else, we are still in the same range. Update the previous number to the current number and continue.
Return the answer array.
Code:-
JAVA Solution
class Solution {
public List<String> summaryRanges(int[] nums) {
List<String> ans = new ArrayList<>();
if (nums.length == 0) {
return ans;
}
StringBuilder s = new StringBuilder(Integer.toString(nums[0]));
int prev = nums[0];
if (nums[nums.length - 1] != -2 && nums[nums.length - 1] != 0) {
nums = Arrays.copyOf(nums, nums.length + 1);
nums[nums.length - 1] = -1;
} else {
nums = Arrays.copyOf(nums, nums.length + 1);
nums[nums.length - 1] = Integer.MAX_VALUE;
}
for (int i = 1; i < nums.length; i++) {
if (Math.abs(nums[i] - prev) != 1) {
if (Integer.parseInt(s.toString()) != prev) {
s.append("->").append(prev);
}
ans.add(s.toString());
s = new StringBuilder(Integer.toString(nums[i]));
}
prev = nums[i];
}
return ans;
}
}
Python Solution
class Solution:
def summaryRanges(self, nums: List[int]) -> List[str]:
ans = []
if len(nums) == 0:
return ans
s = str(nums[0])
prev = nums[0]
if nums[-1] != -2 and nums[-1] != 0:
nums.append(-1)
else:
nums.append(2**31)
for i in nums[1:]:
if abs(i - prev) != 1:
if int(s) != prev:
s += '->'+str(prev)
ans.append(s)
s = str(i)
prev = i
return ans
Complexity Analysis:-
TIME:-
The time complexity is O(n), where n is the length of the nums array.
SPACE:-
The space complexity is also O(n) as we use an additional list (ans) to store the ranges.