Longest Consecutive Sequence

Given an array of integers. Find the length of the longest sub-sequence such that elements in the sub-sequence are consecutive integers, the consecutive numbers can be in any order.

If you are here then chances are you’re trying to find the longest consecutive sequence in an array of integers. The problem can be visualized as follows:

Source: GeeksForGeeks

The above problem could have multiple solutions, but here we will be using a simple approach with O(N) complexity. Here, we will use Tree-Set from Java Collections which are set but store the values in their natural order by sorting them internally at the time of insertion. Although, some might think that sorting while inserting will be done at higher cost of time complexity. But this is the magic of Tree-Set which provides the same implementation in O(log N) times.

How Tree-Set implements insertion in O(log N) ?

In Tree-Set, a self-balancing binary search tree is employed (Red-Black Tree). Therefore, sorting is achieved in the above time complexity while insertion.

Back to our problem, we will insert all our elements of array into a Tree-Set as below:

As of now, we have Tree-Set which contains our numbers in a sorted manner. Now next step would be try to find the longest consecutive sub-sequence in our sorted set.

For this, we will use two variable one would be count to store length of current sub-sequence and max to store the length of our longest consecutive sub-sequence. Now, the remaining task is to run a loop over the Tree-Set and then find out the maximum length of the consecutive sub-sequence.

Here, we have taken prev which will store the previous element and we have initialized it with the first element of the set. Now below are the steps we are following in the iteration:

  1. To check if the number appearing is same as previous, then no need to update anything and we just continue the loop.
  2. If current number (integer) is consecutive to previous number (prev), then we will increment the count by 1. Then, we will check that whether count value is greater than max, if yes then update max with count.
  3. If current number (integer) is not consecutive to previous number (prev), then we will reset the count by 1.
  4. Finally, we will update the value of prev with current number (integer).

Finally, longest consecutive sequence could be found in variable max, and could be returned.

Complexity of the above solution would be O(N), because insertion in Tree-Set would take O(log N) time but the loop for finding the longest consecutive sequence is taking O(N) time, because we are iterating over each element of the treeSet. Hence, in total it would be O(N).

For full source code visit Github repository.

Thanks for reading.

--

--

--

Computer Science (Data Analytics) Graduate at National University of Ireland Galway. https://www.linkedin.com/in/itsparesh

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Sail Laravel 8.0 Debugging with XDebug & PHPStorm

SQL 102: Joins and Join Tables

CSS Cascade summarized

Process, a Love/Hate Relationship

14 language features in TypeScript and Dart you may miss in Java

Day 60: Friends Characters’ Line Counts

What is the Best Hadoop Alternative?

African elephant with zebra stripes — Definitely NOT the Hadoop elephant.

Deploy Python-based Web Apps from GitHub to Azure

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Paresh Krishna Sharma

Paresh Krishna Sharma

Computer Science (Data Analytics) Graduate at National University of Ireland Galway. https://www.linkedin.com/in/itsparesh

More from Medium

Longest Substring Without Repeating Characters📸

Introduction To Merge Sort

LeetCode 199- Binary Tree Right Side View

LeetCode Strobogrammatic Number

The number 619 is strobogrammatic.