Longest Consecutive Sequence

This page explains Java solution to problem Longest Consecutive Sequence using HashMap data structure.

Problem Statement

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.

Solution

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;
    }
}

Time Complexity

O(N) Where
N is total number of elements in an input array.

Space Complexity

O(N) Where
N is total number of elements in an input array.