Using HashMap to Track Boundaries---Easy to understand


  • 1

    The solution uses hashmap to track the boundaries

    1, Only update the neighbors boundary's boundary. 
    2, Use the neighbor to find its boundary. 
    

    The following is the solution:

    public class Solution {
        public int longestConsecutive(int[] nums) {
            if (nums == null) {
                return 0;
            }
            //only update the boundary's range
            HashMap<Integer,int[]> map = new HashMap<Integer,int[]>();
            int max = 0;
            for (int i = 0; i < nums.length;i++) {
                if (!map.containsKey(nums[i])) {
                    if (map.containsKey(nums[i]-1) && map.containsKey(nums[i]+1)) {
                        int[] left = map.get(map.get(nums[i]-1)[0]);
                        int[] right = map.get(map.get(nums[i]+1)[1]);
                        left[1] = right[1];
                        right[0] = left[0];
                        map.put(nums[i],new int[]{left[0],right[1]});
                        max = Math.max(right[1]-left[0]+1, max);
                    } else if (map.containsKey(nums[i]-1)) {
                        int[] left = map.get(map.get(nums[i]-1)[0]);
                        left[1] = nums[i];
                        map.put(nums[i],new int[]{left[0],nums[i]});
                        max = Math.max(nums[i]-left[0] + 1,max);
                    } else if (map.containsKey(nums[i]+1)) {
                        int[] right = map.get(map.get(nums[i]+1)[1]);
                        right[0] = nums[i];
                        map.put(nums[i],new int[]{nums[i],right[1]});
                        max = Math.max(right[1]-nums[i]+1, max);
                    } else {
                        map.put(nums[i], new int[]{nums[i],nums[i]});
                        max = Math.max(1, max);
                    }
                }
            }
            return max;
        }
    }

  • 0

Log in to reply
 

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