Longest Consecutive Sequence in an unsorted array

Basic idea is :

1. Put all the numbers in a hashmap or hashset.

2. Iterate over the array again and for each number find the next consecutive numbers (number+1) while they exists in hashmap. As you find them keep deleting them to avoid duplicate counts. Do the same for previous consecutive numbers(number -1) also.

3. update max count.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37

public class Solution { public int longestConsecutive(int[] nums) { if (nums.length == 0) { return 0; } HashMap<Integer, Integer> hashMap = new HashMap<Integer, Integer>(); int maxNum =1; for(int i = 0; i < nums.length; i++){ hashMap.put(nums[i],i); } for(int i=0; i < nums.length; i++){ int count = 1; int num = nums[i]; int rightNum = num+1; int leftNum = num-1; while(hashMap.containsKey(rightNum)){ System.out.println("increase " +rightNum); count++; hashMap.remove(rightNum); rightNum++; } while(hashMap.containsKey(leftNum)){ System.out.println("increase2 " + leftNum); count++; hashMap.remove(leftNum); leftNum--; } if(count > maxNum){ maxNum = count; } } return maxNum; } }