Sponsored
Sponsored
This approach involves detecting the start and end of each range by iterating through the array sequentially. You remember the start of a potential range and adjust the range's end as long as consecutive numbers are found. When a break in consecutiveness occurs, you fix the end of the current range and start a new one.
Time Complexity: O(n)
Space Complexity: O(n)
1
2#include <stdio.h>
3#include <stdlib.h>
4#include <string.h>
5
6char** summaryRanges(int* nums, int numsSize, int* returnSize) {
7 char **result = (char **)malloc(numsSize * sizeof(char *));
8 *returnSize = 0;
9 int i = 0;
10 while (i < numsSize) {
11 int start = i;
12 while (i + 1 < numsSize && nums[i] + 1 == nums[i + 1]) {
13 i++;
14 }
15 int end = i;
16 char *range = (char *)malloc(25 * sizeof(char));
17 if (start == end) {
18 sprintf(range, "%d", nums[start]);
19 } else {
20 sprintf(range, "%d->%d", nums[start], nums[end]);
21 }
22 result[(*returnSize)++] = range;
23 i++;
24 }
25 return result;
26}
27
The C solution iterates through the sorted array. It uses a start pointer that marks the beginning of a range. If consecutive numbers appear, it keeps adjusting the endpoint of the range. When non-consecutiveness is found (or array ends), it forms a string for that range and starts a new one.
This approach utilizes a two-pointer method where one pointer marks the beginning of a new range, and another pointer (or the loop index itself) expands the range as far as possible until the next number isn't consecutive. Once a sequence ends, if numbers are the same, it is a single-element range; otherwise, a range connecting two different numbers is formed.
Time Complexity: O(n)
Space Complexity: O(n)
1
2
Java's solution also utilizes two pointers, with 'i' marking the start and an additional pointer 'j' expanding as far as consecutiveness permits. Once the range is determined, the results are added to the list as strings.