Consider corner cases where INT_MIN and INT_MAX are involved (Java)


  • 0
    G

    public class MissingRanges {

    @Test
    public void testMissingRanges() {
        MissingRanges obj = new MissingRanges();
        List<String> expect = new ArrayList<String>();
        // case 1
        expect.add("-1->2147483646");
        int[] nums = {Integer.MAX_VALUE};
        List<String> actual1 = obj.findMissingRanges1(nums, -1, Integer.MAX_VALUE);
        List<String> actual2= obj.findMissingRanges2(nums, -1, Integer.MAX_VALUE);
        Assert.assertEquals(false, checker(expect, actual1));
        Assert.assertEquals(true, checker(expect, actual2));
        
        // case2
        expect.clear();
        int[] nums2 = {Integer.MAX_VALUE};
        List<String> actual3 = obj.findMissingRanges1(nums2, Integer.MAX_VALUE, Integer.MAX_VALUE);
        List<String>  actual4= obj.findMissingRanges2(nums2, Integer.MAX_VALUE, Integer.MAX_VALUE);
        Assert.assertEquals(false, checker(expect, actual3));
        Assert.assertEquals(true, checker(expect, actual4));
    }
    public boolean checker(List<String> expect, List<String> actual) {
        if (expect.size() != actual.size())
            return false;
        for (int i = 0; i < expect.size(); i++) {
            if (!expect.get(i).equals(actual.get(i)))
                return false;
        }
        return true;
    }
    // more robust version, take care of overflow edge case 
    public List<String> findMissingRanges2(int[] nums, int lower, int upper) {
        List<String> ret = new ArrayList<String>();
        if (nums == null)
            return ret;
        for (int i = 0; i < nums.length; i++) {
            if (lower < nums[i]) {
                if (lower < nums[i] - 1) {// avoid overflow
                    ret.add("" + lower + "->" + (nums[i] - 1));
                } else {
                    ret.add(String.valueOf(lower));
                }
            }
            if (nums[i] < Integer.MAX_VALUE) // avoid overflow
                lower = nums[i] + 1;
            else
                lower = Integer.MAX_VALUE;
        }
        // process lower==upper for case like: [-1], -1, 0
        // check nums[nums.length -1] != Integer.MAX_VALUE for case like:
        // [Integer.MAX_VALUE], Integer.MAX_VALUE, Integer.MAX_VALUE
        if (lower < upper) {
            ret.add("" + lower + "->" + upper);
        } else if (lower == upper && !(nums.length > 0 && nums[nums.length -1] == Integer.MAX_VALUE))  {
            ret.add(String.valueOf(lower));
        }
        return ret;
    }
    
    // base version
    public List<String> findMissingRanges1(int[] nums, int lower, int upper) {
        List<String> ret = new ArrayList<String>();
        if (nums == null)
            return ret;
        for (int i = 0; i < nums.length; i++) {
            if (lower < nums[i]) {
                if (nums[i] - lower > 1) {
                    ret.add("" + lower + "->" + (nums[i] - 1));
                } else {
                    ret.add(String.valueOf(lower));
                }
            }
            lower = nums[i] + 1;
        }
        if (lower < upper) {
            ret.add("" + lower + "->" + upper);
        } else if (lower == upper) {
            ret.add(String.valueOf(lower));
        }
        return ret;
    }
    

    }


Log in to reply
 

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