Tuesday, August 18, 2015

Leetcode: Summary Ranges

Given a sorted integer array without duplicates, return the summary of its ranges.
For example, given [0,1,2,4,5,7], return ["0->2","4->5","7"].
Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.
Analysis:
The problem itself is very simple. The only thing needs to be careful is if the range contains only one element, it cannot contain the right arrow "->". 

Code (Java):
public class Solution {
    public List<String> summaryRanges(int[] nums) {
        List<String> results = new ArrayList<String>();
        if (nums == null || nums.length == 0) {
            return results;
        }
        
        if (nums.length == 1) {
            String temp = Integer.toString(nums[0]);
            results.add(temp);
            return results;
        }
        
        int lo = 0; 
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] - nums[i - 1] == 1) {
                continue;
            } else {
                StringBuffer sb = new StringBuffer();
                sb.append(Integer.toString(nums[lo]));
                if (i - lo > 1) {
                    sb.append("->");
                    sb.append(Integer.toString(nums[i - 1]));
                }
                results.add(sb.toString());
                lo = i;
            }
        }
        
        // Handle the trailing numbers
        if (lo < nums.length) {
            StringBuffer sb = new StringBuffer();
            sb.append(nums[lo]);
            if (nums.length - lo > 1) {
                sb.append("->");
                sb.append(Integer.toString(nums[nums.length - 1]));
            }
            results.add(sb.toString());
        }
        
        return results;
    }
}


Update on 10/20/15:
Be very careful about the overflow might happen at nums[i] - nums[i - 1], e..g. nums[i] = Integer.MAX_VALUE, nums[i - 1] = Integer.MIN_VALUE. 
public class Solution {
    public List<String> summaryRanges(int[] nums) {
        List<String> result = new ArrayList<>();
        
        if (nums == null || nums.length == 0) {
            return result;
        }
        
        if (nums.length == 1) {
            String s = nums[0] + "";
            result.add(s);
            return result;
        }
        
        int j = 0;
        for (int i = 1; i < nums.length; i++) {
            if ((long) nums[i] - (long) nums[i - 1] > 1) {
                calculateRanges(j, i - 1, nums, result);
                j = i;
            }
        }
        
        calculateRanges(j, nums.length - 1, nums, result);
        
        return result;
    }
    
    private void calculateRanges(int lo, int hi, int[] nums, List<String> result) {
        StringBuffer sb = new StringBuffer();
        
        if (lo == hi) {
            sb.append(nums[lo]);
            result.add(sb.toString());
        } else {
            sb.append(nums[lo]);
            sb.append("->");
            sb.append(nums[hi]);
            result.add(sb.toString());
        }
    }
}

Update on 1/18/16:
public class Solution {
    public List<String> summaryRanges(int[] nums) {
        List<String> result = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            return result;
        }
        
        if (nums.length == 1) {
            String curr = nums[0] + "";
            result.add(curr);
            return result;
        }
        
        // General case
        int j = 0;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] - nums[i - 1] != 1) {
                String curr = generateRange(nums, j, i - 1);
                result.add(curr);
                j = i;
            }
        }
        
        // Final case
        String curr = generateRange(nums, j, nums.length - 1);
        result.add(curr);
        
        return result;
    }
    
    private String generateRange(int[] nums, int start, int end) {
        if (start > end) {
            return "";
        }
        
        if (start == end) {
            String curr = nums[start] + "";
            return curr;
        }
        
        String curr = nums[start] + "->" + nums[end];
        return curr;
    }
}

No comments:

Post a Comment