High space consumption with O(n) time complexity


  • 0
    W
    public class Solution {
    class range{
        public int start;
        public int end;
        public int count;
        public range(int start, int end){
            this.start = start;
            this.end = end;
            count = 1;
        }
    }
    public int longestConsecutive(int[] nums) {
        Map<Integer, range> hm = new HashMap<Integer, range>();
        Set<Integer> check = new HashSet<Integer>();
        if (nums == null || nums.length == 0) return 0;
        int max = 1;
        for (int i = 0; i < nums.length; i++){
            if (check.contains(nums[i])) continue;
            check.add(nums[i]);
            int before = nums[i] - 1;
            int after = nums[i] + 1;
            if (hm.containsKey(before)) {
                range r = hm.get(before);
                r.end = nums[i];
                r.count++;
                max = Math.max(r.count, max);
                if (hm.containsKey(after)) {
                    range r1 = hm.get(after);
                    r1.start = r.start;
                    r.end = r1.end;
                    r.count = r.count + r1.count;
                    r1.count = r.count;
                    hm.put(r.start, r);
                    hm.put(r.end, r);
                    max = Math.max(r.count, max);
                }
                else hm.put(r.end, r);
            }
            else if (hm.containsKey(after)){
                range r2 = hm.get(after);
                r2.start = nums[i];
                r2.count++;
                max = Math.max(r2.count, max);
                hm.put(r2.start, r2);
            }
            else{
                range newrange = new range(nums[i], nums[i]);
                hm.put(nums[i], newrange);
            }
        }
        return max;
    }
    

    }


Log in to reply
 

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