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}
27The 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
The two-pointer approach in C keeps two indices. The starting pointer begins a new potential range. The other adjusts as long as numbers are consecutive. Once they diverge, it involves forming a possible range string or single number and returning when done.