@@ -0,0 +1,979 @@
+package com.interview.array;%0A%0Aimport java.util.HashMap;%0Aimport java.util.Map;%0A%0A/**%0A * Date 12/03/2016%0A * @author Tushar Roy%0A *%0A * Find longest consecutive subsequence in unsorted array.%0A *%0A * Time complexity O(n)%0A * Space complexity O(n)%0A * %0A * Reference%0A * https://leetcode.com/problems/longest-consecutive-sequence/%0A */%0Apublic class LongestConsecutiveSubsequence %7B%0A    public int longestConsecutive(int%5B%5D nums) %7B%0A        Map%3CInteger, Integer%3E map = new HashMap%3CInteger, Integer%3E();%0A        int result = 1;%0A        for (int i : nums) %7B%0A            if (map.containsKey(i)) %7B%0A                continue;%0A            %7D%0A            int left = map.containsKey(i - 1) ? map.get(i - 1) : 0;%0A            int right = map.containsKey(i + 1) ? map.get(i + 1) : 0;%0A%0A            int sum = left + right + 1;%0A            map.put(i, sum);%0A            result = Math.max(sum, result);%0A            map.put(i - left, sum);%0A            map.put(i + right, sum);%0A        %7D%0A        return result;%0A    %7D%0A%7D

longest consecutive subsequence