Tc : O(nlogn) for sorting the intervals array + O(25) for other iterations

Sc :O(n) for using List

```
class Solution {
public List<Integer> partitionLabels(String s) {
int intervals[][] = new int[26][2];
for(int i =0;i<intervals.length;i++){
intervals[i][0] = 501;
intervals[i][1] = -1;
}
for(int i = 0;i<s.length();i++){
char c = s.charAt(i);
int index = c-'a';
intervals[index][0] = Math.min(intervals[index][0],i);
intervals[index][1] = Math.max(intervals[index][1],i);
}
//sorting
Arrays.sort(intervals,(a,b)-> a[0]-b[0]);
//merging
int start = intervals[0][0];
int end = intervals[0][1];
List<Integer> list = new ArrayList<>();
for(int i =1;i<intervals.length;i++){
if(intervals[i][0]==501) break;// exit as no need to traverse any further
if(end >= intervals[i][0]){
start = Math.min(intervals[i][0],start);
end = Math.max(intervals[i][1],end);
}
else{
list.add(end-start+1); // instead of keeping the range [start, end] in the list we are addting their sizes
start = intervals[i][0];
end = intervals[i][1];
}
}
list.add(end-start+1);
return list;
}
}
```

## Top comments (0)