Monday, January 18, 2016

Indeed: 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.

Understand the problem:
Note that the sorted integer array does not contain any duplicates. 

Code (Java):
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;
    }
}

Follow-up: What if the input contains duplicate numbers?
e.g. [1,2,2,3] -> "1->3"
[1,2,2,5] -> "1->2", "5"


For the input containing duplicates, we only need to slightly modify the code that only skips the duplicated numbers as well.

Code (Java):
import java.io.*;
import java.util.*;

/*
 * To execute Java, please define "static void main" on a class
 * named Solution.
 *
 * If you need more classes, simply define them inline.
 */

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) || (nums[i] == nums[i - 1])) {
                continue;
            }
                
            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;
    }
                
    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] nums = new int[]{1,2,2,5};
        List<String> result = sol.summaryRanges(nums);
        
        for (String str : result) {
            System.out.println(str);
        }
    }
}

No comments:

Post a Comment