Longest Consecutive Subsequence in a stream of integers

Question

Given a stream of array, for each element we have to find the longest consecutive subsequence till now

For example:

10 -> 1

12 -> 1

11 -> 3 (10,11,12)

20 -> 3

What I think: Create a set and for each incoming number, check what if its the start/end of the LCS. Take the max possible length.

Since this is of O(N^2), is there any possible way to reduce the TC? I don't need the code but just a way to optimize the algo

If you treat each incoming number `x` as an interval `[x, x+1]`, you can use a data structure for storing maximal disjoint intervals as explained [in this post.](https://stackoverflow.com/questions/1982409/data-structure-for-handling-intervals) They recommend an interval tree, which uses a balanced BST to solve this in `O(log n)` time per operation. You just need to store the maximum interval length as well. — kcsquared, Feb 09 '22 at 14:23
11 -> 3 (10,11,12) , shouldn't it be 10,12,11 ? I quite didn't understand the example — Anurag, Feb 10 '22 at 07:21

score 0 · Answer 1 · answered Feb 11 '22 at 08:09

You can do this in O(n log n) time with a balanced BST using the ideas from this post.

An incoming number x will be treated as an interval [x, x+1]. The BST stores the boundary points of the disjoint intervals; each leaf node in the BST should also store whether it's a start or end, and the length of the interval it's part of.

When a point x comes in, search the BST for the largest element u <= x. If it's present and it's a 'start point', continue. Also search for the smallest element x + 1 <= v. If it's present and it's an 'end point', continue.

Otherwise, there's several cases. If x is an end point and x+1 is a start point, you should remove both from the BST, forming a new interval whose size is the sum of the two combined intervals + 1. If one of (x is an end point, x+1 is a start point) is true, remove that point, and extend the appropriate interval by 1 to the right or left, respectively. If [x, x+1] is already contained in an interval, continue. Otherwise, add x and x+1 to the BST as a start and end, respectively, of size 1.

On each addition, you'll check whether the new interval is larger than the previous largest: if so, and u, v are the boundary points, your longest consecutive subsequence is u, u+1, ... v-1.

score 0 · Answer 2 · answered Nov 22 '22 at 23:10

let numbers = [1, 3, 4, 2, 7, 8, 10, 12, 5, 15];
numbers.sort((a, b) => a - b);
let chunks = [[]];
let prev = 0;
numbers.forEach(current => {
  if(current - prev !== 1) chunks.push([]);
  chunks[chunks.length - 1].push(current);
  prev = current;
});
chunks.sort((a, b) => b.length - a.length);
let result = chunks[0];

console.log('Items: ', result);
console.log('Max length: ', result.length);

Longest Consecutive Subsequence in a stream of integers

2 Answers2