This page explains Java solution to problem Longest Consecutive Sequence
using HashMap
data structure.
Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
Your algorithm should run in O(n)
complexity.
Input: [100, 4, 200, 1, 3, 2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.
package com.vc.hard;
import java.util.*;
class LongestConsecutiveSequence {
public int longestConsecutive(int[] nums) {
HashMap<Integer, Integer> map = new HashMap<>();
int res = 0;
for(int i = 0; i < nums.length; i++) {
if(map.containsKey(nums[i])) continue;
int left = map.getOrDefault(nums[i] - 1, 0);
int right = map.getOrDefault(nums[i] + 1, 0);
int total = left + right + 1;
map.put(nums[i], total);
map.put(nums[i] - left, total);
map.put(nums[i] + right, total);
res = Math.max(res, total);
}
return res;
}
}
O(N) Where
N is total number of elements in an input array.
O(N) Where
N is total number of elements in an input array.