Leetcode Longest Consecutive Sequence problem solution

YASH PAL,

In this Leetcode Longest Consecutive Sequence problem solution we have Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence. You must write an algorithm that runs in O(n) time.

leetcode longest consecutive sequence problem solution

Problem solution in Python.

def longestConsecutive(self, nums):
        
        def get_parent(val, P):
            if P[val] == val: return val
            P[val] = get_parent(P[val], P)
            return P[val]
        
        def union(u, v, S, P):
            U, V = get_parent(u, P), get_parent(v, P)
            P[V], S[U] = P[U], S[U] + S[V]
            return S[U]
        
        if not nums: return 0
        S, P = {}, {}
        mx = 1
        for n in nums:
            if n not in P:
                S[n], P[n] = 1, n
                if n+1 in P: mx = max(mx, union(n, n+1, S, P))
                if n-1 in P: mx = max(mx, union(n-1, n, S, P))
        return mx

Problem solution in Java.

public int longestConsecutive(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for(int i : nums) set.add(i);
        Set<Integer> vis = new HashSet<>();
        int curCount = 0, sofarMax = 0;
        for(int i:set){
            if(vis.contains(i)) continue;
            int tmp = i;
            while(set.contains(++tmp)){
                curCount++;
                vis.add(tmp);
            }
            tmp = i;
            while(set.contains(--tmp)){
                curCount++;
                vis.add(tmp);
            }
            vis.add(i);
            curCount++;
            sofarMax = Math.max(curCount,sofarMax);
            curCount = 0;
        }
        return sofarMax;

Problem solution in C++.

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> s;

        if(nums.size()==0){
            return 0;
        }
        for(int i=0;i<nums.size();i++){
            s.insert(nums[i]);
        }
        
        
        int count=1;
        for(int i=0;i<nums.size();i++){
            if(!s.count(nums[i]-1)){
                int curr_num=nums[i];
                int curr_count=0;
                while(s.find(curr_num)!=s.end()){
                    curr_count++;
                    curr_num++;
                }
                count=max(count,curr_count);
            }
        }
        return count;
        
    }
};

Problem solution in C.

int longestConsecutive(int* nums, int numsSize) {
    if(numsSize<=1) return numsSize;
    int gap=0;
    int i,j;
    for(gap=numsSize/2;gap>=1;gap=gap/2){
        for(i=gap;i<numsSize;i++){
            for(j=i-gap;j>=0&&nums[j]>nums[j+gap];j=j-gap){
                int temp=nums[j];
                nums[j]=nums[j+gap];
                nums[j+gap]=temp;
            }
        }
    }
    int temp;
    int ret=1;
    i=1;
    while(i<numsSize){
        temp=1;
        if(nums[i]-nums[i-1]==1){
        while((nums[i]-nums[i-1]==1||nums[i]-nums[i-1]==0)&&i<numsSize) 
        {
            if(nums[i]-nums[i-1]==1) temp++;
            i++;
        }
        }else if(nums[i]-nums[i-1]==-1){
        while((nums[i]-nums[i-1]==-1||nums[i]-nums[i-1]==0)&&i<numsSize)
        {
            if(nums[i]-nums[i-1]==-1) temp++;
            i++;
        }
        }
        if(temp>ret) ret=temp;
        i++;
    }
    return ret;
}

coding problems