My java solution with O(n)


  • 0
    S
    public class Solution {
        public int longestConsecutive(int[] nums) {
            int boundary = nums.length;
            List<Bucket> bucks = new ArrayList<Bucket>();
            for(int n:nums)
            {
                boolean newBuck = true;
                for(Bucket b:bucks)
                {
                    if(Math.abs(b.firstNumber - n) < boundary)
                    {
                        b.add(n);
                        newBuck = false;
                    }
                }
                if(newBuck)
                {
                    bucks.add(new Bucket(n,boundary));
                }
            }
            
            int max = 1;
            
            for(Bucket bk: bucks)
            {
            
            int[] cnt = bk.cnt;
            int start = 0;
            int end = 0;
            boolean counting = false;
            
            for(int i = 0; i< cnt.length; i++)
            {
                if(cnt[i] > 0)
                {
                    if(counting)
                    {
                        end++;    
                    }
                    else
                    {
                        counting = true;
                        start = i;
                        end = i;
                    }
                    
                }
                else
                {
                    if(counting)
                    {
                        counting = false;
                        int tmp = 0;
                        for(int j=start; j<=end;j++)
                        {
                            tmp +=cnt[j];
                        }
                        if(max < tmp)
                        {
                            max = tmp;
                        }
                    }
                    else
                    {
                        start++;
                        end++;
                    }
                }
            }
            
            if(counting)
            {
                 int tmp = 0;
                        for(int j=start; j<=end;j++)
                        {
                            tmp +=cnt[j];
                        }
                        if(max < tmp)
                        {
                            max = tmp;
                        }
            }
            
            
            
            }
        
            
            return max;
            
        }
    }
    
    
    class Bucket
    {
        public int[] cnt;
        public int firstNumber;
        public int bound;
        
        public Bucket(int first, int bound)
        {
            this.firstNumber = first;
            this.bound = bound;
            cnt = new int[bound*2-1];
            add(first);
        }
        
        public void add(int i)
        {
            cnt[i-firstNumber+bound-1]=1;
        }
       
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.