LeetCode 228: Summary Ranges Solution in Java (Time: O(n))

Difficulty: Easy

Topics: Array

Platform: Leetcode

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" if a != b
"a" if a == b

Problem Statement Simplified

Get back the range of continuous numbers in the array.

Mistakes and Learning

1. Forgot to check for the leftover at the end of the for loop — always need to check the end-of-data scenario.
2. Forgot to check if nums. length is 0 or not—always need to check if the nums array has any element in it.

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"

Key Insight

1. If the array is not empty, loop through it.
2. While i+1 is less than nums.length and nums[i+1] equals nums[i+1]+1, then i++.
3. Else, add to the list.

Algorithm

1. Initialize a list to store the range.
2. Check if the nums is empty if yes then return list.
3. Loop through the nums.
4. Initialize a start variable and assign nums[i] to it.
5. while i+1 is less than nums.length and nums[i] equals num[i]+1.
6. Then i++.
7. End while.
8. If start is not equal to nums[i] then add first -> nums[i] to the list.
9. Else, convert to string value and add to list
10. End if.
11. End for.
12. Return list.

Algorithm in simple words

First, initialize a list to store the range, then check if nums is empty if empty, then return the list else we can continue.

Loop through the nums and assign the current value to an int, start. While i+1 is less than total length and nums[i]=nums[i]+1, then i++, ie goto the next value, because this is a continuous number.

So when nums[i] != nums[i]+1 or have reached the end of the array, we will check if start!=num[i] — that means to check if start and current value is same or not; if they are not the same, then add start + "->" + nums[i] to the list

If they are same, then convert the int to a string and add to the list. And return the list.

Java code

class Solution {
    public List<String> summaryRanges(int[] nums) {

        List <String> result= new ArrayList<>();
        if(nums.length==0){
            return result;
        }
    for(int i=0;i<nums.length;i++){
       int start= nums[i];
       while(i+1<nums.length && nums[i+1]==nums[i]+1){
        i++;
       }
       if(start!=nums[i]){
        result.add(start+"->"+nums[i]);
       }
       else{
        result.add(String.valueOf(start));
       }
    }return result;
    }
}

Time & Space Complexity

Time Complexity: O(n)

Space Complexity: O(n)