Find the longest consecutive sequence in O(n) complexity

Hey Geeks, I’m so glad to see you here. I was surfing the internet and found this problem. Finding the longest consecutive sequence in O(n) complexity is hard.

I thought, let’s give it a try, cause why not? I did this code as much as I understood. Even I don’t know how to calculate the exact complexity of this code. Oh no! I told you something kept secret. Shit! But if you find any bug or if you have a better idea to solve this, let me know. Yeah? yeah.

Anyway, enough of talking, let’s dig in.

Problem Statement

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
For example, given [100, 4, 200, 1, 3, 2], the longest consecutive element sequence is [1, 2, 3, 4]. Return its length: 4.
Your algorithm should run in O(n) complexity.

Solution

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package code1;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 *
 * @author Shankha
 */
public class LongestConsecutiveElementsSequence {

    public static void main(String[] args) {
//        int[] array2 = {};                                    // Expected 0
//        int[] array2 = {0};                                   // Expected 0
//        int[] array2 = {0, 0};                                // Expected 1
//        int[] array2 = {0,-1};                                // Expected 2
//        int[] array2 = {1, 2, 0, 1};                          // Expected 3
//        int[] array2= {100,4,200,1,3,2};                      // Expected 4
        int[] array2 = {9, 1, 4, 7, 3, -1, 0, 5, 8, -1, 6};     // Expected 7

        System.out.println(longestConsecutive(array2));
    }

    public static int longestConsecutive(int[] nums) {

        Integer[] array = Arrays.stream(nums).boxed().toArray(Integer[]::new);

        if (array.length == 0) {
            return 0;
        } else if (array.length == 1) {
            return 1;
        }

        List<Integer> list = new ArrayList<>();

        list.addAll(Arrays.asList(array));

        Collections.sort(list);

        int maxSeqCnt = 0;
        int tempCnt = 0;
        for (int i = 0; i < list.size() - 1; i++) {
            if (list.get(i) == list.get(i + 1)) {
                continue;
            }
            if (list.get(i) + 1 == list.get(i + 1)) {
                tempCnt++;
                maxSeqCnt = (maxSeqCnt > tempCnt) ? maxSeqCnt : tempCnt;
            } else {
                tempCnt = 0;
            }
        }

        return maxSeqCnt + 1;

    }
}

 

That’s it. Loved it? Now do me a favor, please share this post to your friends and like this post. If something is wrong, please let me know in the comments below.

Are you interested in DBMS? Then I would recommend you to read this post below, you will love it.

Which datatype is used to store pictures and how?

Leave a Reply