O(n) Optimized Java solution with detailed explanation on both requirement and solution


  • 1
    L

    In fact this question is not difficulty at all. But the requirement description is too short and the example is not support you fully understand the question as well. According to my testing, I appended the requirement as below:
    Requirement:

    1. What is range? A range means each element equals previous element +1. For example, 0,1,2,3. If one element plus one not equal to the successive element then, then they belong to different range. For instance, [0,1,2,5,6] contains two ranges [0,1,2] and [5,6]
    2. How to represent a range? The range range follows the pattern of "start[->end]". If the range has only one element, then without [->end]. For example, the range of [5,6,7] is "5->7" not "5->6->7"
    public List<String> summaryRanges(int[] nums) {
            LinkedList<String> list = new LinkedList<String>();
            if (nums == null || nums.length == 0) return list;
    
            //Define the start point of the next range
            int start = 0;
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < nums.length; i++) {
    
                //Put the first element into the StringBuilder
                if (i == start) sb.append(nums[i]);
    
                if (i + 1 < nums.length && nums[i + 1] == nums[i] + 1) {
                    //If "[i+1]=[i]+1" then they are in the same range, append "->[i+1]"
    
                    if(i + 2 < nums.length && nums[i + 2] == nums[i+1] + 1) {
                        //NOT at the end of range, skip.
                        // e.g [0,1,2,3] output should be [0->3] rather than [0->1->2->3]
                        continue;
                    } else {
                        //At the end of current range
                        sb.append("->").append(nums[i + 1]);
                    }
    
                } else {
                    //Not continue, start a new range.
                    start = i + 1;              //Update start point for the next next range
                    list.add(sb.toString());    //Add current range string into list
                    sb.setLength(0);            //Reset StringBuilder
                }
            }
    
            return list;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.