Leetcode 228. Summary Ranges
Problem Explanation:
The problem requires us to take a sorted array of numbers (without duplicates) and summarize the continuous ranges within it. A continuous range
in this context means a sequence of numbers that increment by one. For example, [2,3,4] is a continuous range, but [2,4] is not. Our task is to provide the start and end of each continuous range. If the range only includes one number, then we only need to provide this number.
Let's take the first example from the problem:
1 2 3Input: [0,1,2,4,5,7]
For this input, we have three continuous ranges, being: 0->2
, 4->5
, and 7
. As such, the output would be: ["0->2","4->5","7"]
.
Solution Approach:
The solution iterates through the array, marking the beginning of each identified range. If the next number in the array is exactly one greater than the current number, this sustain the range and so the loop proceeds, until a break in the range is found.
When a break in range is found, both the start and the end of the range are known, so they are added as part of the answer. If the range consists of only one number, only that number is added.
Python Solution:
1 2python 3class Solution: 4 def summaryRanges(self, nums: List[int]) -> List[str]: 5 if not nums: 6 return [] 7 res, i, start = [], 0, 0 8 while i < len(nums)-1: 9 if nums[i] != nums[i+1]-1: 10 res.append(self.printRange(nums[start], nums[i])) 11 start = i+1 12 i+=1 13 res.append(self.printRange(nums[start], nums[i])) 14 return res 15 def printRange(self, lower: int, upper: int) -> str: 16 if lower==upper: 17 return str(lower) 18 else: 19 return str(lower)+"->"+str(upper)
Java Solution:
1 2java 3class Solution { 4 public List<String> summaryRanges(int[] nums) { 5 List<String> result = new ArrayList<String>(); 6 for (int i = 0; i < nums.length; i++) { 7 int start = nums[i]; 8 while (i + 1 < nums.length && nums[i] == nums[i + 1] - 1) 9 i++; 10 if (start != nums[i]) 11 result.add(start + "->" + nums[i]); 12 else 13 result.add(start + ""); 14 } 15 return result; 16 } 17}
Javascript Solution:
1 2javascript 3var summaryRanges = function(nums) { 4 const output = []; 5 let rangeStartIndex = 0; 6 for(let i = 1; i <= nums.length; i++){ 7 if(nums[i - 1] + 1 !== nums[i]){ 8 output.push(nums[rangeStartIndex] + (rangeStartIndex < i - 1? '->' + nums[i - 1]: '')); 9 rangeStartIndex = i; 10 } 11 } 12 return output; 13};
C++ Solution:
1
2cpp
3class Solution {
4public:
5 vector<string> summaryRanges(vector<int>& nums) {
6 vector<string> result;
7 for (int i = 0; i < nums.size(); i++) {
8 int start = nums[i];
9 while (i + 1 < nums.size() && nums[i] == nums[i + 1] - 1)
10 i++;
11 if (start != nums[i])
12 result.push_back(to_string(start) + "->" + to_string(nums[i]));
13 else
14 result.push_back(to_string(start));
15 }
16 return result;
17 }
18};
C# Solution:
1
2csharp
3public class Solution {
4 public IList<string> SummaryRanges(int[] nums) {
5 List<string> result = new List<string>();
6 for (int i = 0; i < nums.Length; i++) {
7 int start = nums[i];
8 while (i + 1 < nums.Length && nums[i] == nums[i + 1] - 1)
9 i++;
10 if (start != nums[i])
11 result.Add(start + "->" + nums[i]);
12 else
13 result.Add(start + "");
14 }
15 return result;
16 }
17}
All these solutions offer a time complexity of O(n), where n is the length of the input array. They simply iterate over the array once, identifying and processing each range in turn.## Rust Solution:
Rust is another modern and efficient language for performing such tasks with type safety. Below is the solution for the given problem using Rust.
1
2rust
3pub fn summary_ranges(nums: Vec<i32>) -> Vec<String> {
4 let mut result: Vec<String> = vec![];
5 let (mut i, n) = (0, nums.len());
6 while i < n {
7 let start = i;
8 i += 1;
9 while i < n && nums[i] == nums[i - 1] + 1 {
10 i += 1;
11 }
12 let end = i - 1;
13 let range = if start == end {
14 nums[start].to_string()
15 } else {
16 format!("{}->{}", nums[start], nums[end])
17 };
18 result.push(range);
19 }
20 result
21}
In Rust, list values are accessed using the index and the to_string()
method is used to convert the integer values to string. The format!()
macro is used to format the strings with dynamic values.
Swift Solution:
Swift is a powerful and intuitive language that is used for iOS, macOS, watchOS and tvOS app development. Here is a simple solution to our task using Swift.
1 2swift 3class Solution { 4 func summaryRanges(_ nums: [Int]) -> [String] { 5 var result = [String]() 6 var i = 0 7 while i < nums.count { 8 var start = nums[i] 9 while i < nums.count-1 && nums[i] == nums[i+1] - 1 { 10 i += 1 11 } 12 if start != nums[i] { 13 result.append("\(start)->\(nums[i])") 14 } else { 15 result.append("\(start)") 16 } 17 i += 1 18 } 19 return result 20 } 21}
Swift takes a more type-safe approach to programming, due to which we have to explicitly cast the integer values to strings. Here "\()"
is used as a string interpolation to insert values into strings.
Problem-solving is always a fun task for programmers, and learning to solve them in different programming languages enhances one's coding skills and ability to think logically and efficiently.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.