Problem

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

Example

Given [100, 4, 200, 1, 3, 2], the longest consecutive elements sequence should be [1, 2, 3, 4]. Its length is 4.

The algorithm should run in O(n) complexity.

JavaScript Code

function longestConsecutive(num) {
    // if array is empty, return 0
    if (num.length == 0) {
        return 0;
    }
 
    var set = [];
    var max = 1;
 
    for (var i=0; i<num.length; i++)
        set.push(num[i]);
 
    for (var i=0; i<num.length; i++) {
        var left = num[i] - 1;
        var right = num[i] + 1;
        var count = 1;
 
        while (set.indexOf(left) != -1) {
            count++;
            set.splice(set.indexOf(left), 1);
            left--;
        }
 
        while (set.indexOf(right) != -1) {
            count++;
            set.splice(set.indexOf(right), 1);
            right++;
        }
 
        max = Math.max(count, max);
    }
 
    return max;
}

console.log(longestConsecutive([4,3,2,0,8]));

0 comments:

Blogroll

Follow this blog by Email

Popular Posts