package com.interview.array;

import java.util.HashMap;
import java.util.Map;

/**
 * Date 12/03/2016
 * @author Tushar Roy
 *
 * Find longest consecutive subsequence in unsorted array.
 *
 * Time complexity O(n)
 * Space complexity O(n)
 * 
 * Reference
 * https://leetcode.com/problems/longest-consecutive-sequence/
 */
public class LongestConsecutiveSubsequence {
    public int longestConsecutive(int[] nums) {
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        int result = 1;
        for (int i : nums) {
            if (map.containsKey(i)) {
                continue;
            }
            int left = map.containsKey(i - 1) ? map.get(i - 1) : 0;
            int right = map.containsKey(i + 1) ? map.get(i + 1) : 0;

            int sum = left + right + 1;
            map.put(i, sum);
            result = Math.max(sum, result);
            map.put(i - left, sum);
            map.put(i + right, sum);
        }
        return result;
    }
}
@@ -233,17 +233,16 @@
  O(n)%0A *
- 
 %0A * Refe
@@ -969,10 +969,248 @@
 t;%0A    %7D
+%0A%0A    public static void main(String args%5B%5D) %7B%0A        LongestConsecutiveSubsequence lcs = new LongestConsecutiveSubsequence();%0A        int%5B%5D input = %7B100, 4, 200, 1, 3, 2%7D;%0A        System.out.println(lcs.longestConsecutive(input));%0A    %7D
 %0A%7D

add main function to longest consecutive subsequence