Summary Ranges Leetcode Solution

Difficulty Level Easy
Frequently asked in Facebook Yandex
algorithms Array coding Interview interviewprep LeetCode LeetCodeSolutionsViews 7021

Problem Statement

In Summary Ranges problem a sorted unique integer array is given. We have to make smallest sorted list of ranges that cover all numbers in array exactly once i.e. each element of array is covered by exactly one of the ranges.

Each range [a,b] in the list should be output as:

“a->b” if a != b
“a” if a == b

Example

nums = [0,1,2,4,5,7]
["0->2","4->5","7"]

Explanation:

The ranges are:
“0->2”   covers  numbers { 0 , 1 , 2 }
“4->5”  covers numbers { 4 , 5 }
“7”  covers numbers { 7 }

Hence it covers all numbers of array exactly once.

nums = [0,2,3,4,6,8,9]
["0","2->4","6","8->9"]

Explanation:

The ranges are:
[0,0] –> “0”
[2,4] –> “2->4”
[6,6] –> “6”
[8,9] –> “8->9”

Approach

As stated above we have to make smallest list of ranges. Therefore if two adjacent elements differ by 1 difference then it must belong to same range. On the other hand if two adjacent elements have difference greater than 1, then they can’t belong to same range.

Summary Ranges Leetcode Solution

So now algorithm is simple. We have to traverse for each adjacent elements. If difference between the two adjacent numbers is greater than 1 then we have to make a new range for the second number. Otherwise if the difference is exactly 1 then we will put that number in same range.

Algorithm

  1. Create a list of string to store the result.
  2. Start traversing the array from i=0 till i<N, (N is the size of array) in a while loop.
    • Mark the number at current index as start of the range.
    • Traverse the array starting from current index and find the last element whose difference from previous element is exactly 1, i.e. nums[i+1]==nums[i]+1
    • Mark this element as end of the range.
    • Now insert this formed range into the result list. And repeat for the remaining elements.
  3. Return the result list.

Implementation

C++ Program for Summary Ranges Leetcode Solution

#include <bits/stdc++.h>
using namespace std;

vector<string> summaryRanges(vector<int>& nums) 
{
    vector<string> res;
    int i=0,n=nums.size();
    while(i<n)
    {
        int start,end;

        start=nums[i];            
        while(i+1<n && nums[i+1]==nums[i]+1) i++;
        end=nums[i];

        if(start==end)
            res.push_back(to_string(start));
        else
            res.push_back(to_string(start) + "->" + to_string(end));

        i++;
    }

    return res;
}

int main() 
{   
    vector<int> nums={0,1,2,4,5,7};
    vector<string> res= summaryRanges(nums);
    
    for(auto str:res) cout<< str <<endl;
    
    return 0; 
}

0->2
4->5
7

Java Program for Summary Ranges Leetcode Solution

import java.util.*;
class Rextester{
    
    public static List<String> summaryRanges(int[] nums) 
    {      
        List<String> res= new ArrayList<String>();
        
        int i=0,n=nums.length;
        while(i<n)
        {
            int start,end;
            
            start=nums[i];            
            while(i+1<n && nums[i+1]==nums[i]+1) i++;
            end=nums[i];
            
            if(start==end)
                res.add(start + "");
            else
                res.add( start + "->" + end );
            
            i++;          
        }
        
        return res;
    }
    
  public static void main(String args[])
    {
        int[] nums={0,1,2,4,5,7};
        List<String> res= summaryRanges(nums);
        
        for(String str:res)
            System.out.println(str);
    }
}

0->2
4->5
7

Complexity Analysis for Summary Ranges Leetcode Solution

Time Complexity

O(N) : Where N is the size of the given array. Although we are using two nested loops but every element is visited only once. Hence time complexity is O(N).

Space Complexity 

O(1) : We are not using any auxiliary space except for returning the list of strings.

Translate »