Python in o(n) using dict


#1
class Solution:
    # @param A : tuple of integers
    # @return an integer
    def longestConsecutive(self, A):
        d={}
        for i in A:
            if i in d:
                continue
            if i-1 in d and i+1 in d:
              top_idx=d[i+1][1]
              low_idx=d[i-1][0]
              d[low_idx]=[low_idx,top_idx,d[top_idx][2]+d[low_idx][2]+1]
              d[top_idx]=d[low_idx]
            elif i+1 in d:
              idx=d[i+1][1]
              d[i]=[i,d[idx][1],d[idx][2]+1]
              d[idx]=d[i]
            elif i-1 in d:
              d[i]=[d[i-1][0],i,d[i-1][2]+1]
              low_idx=d[i-1][0]
              d[low_idx]=d[i]
            else:
              d[i]=[i,i,1]
        m=0
        for val in d.values():
          if (val[2]>m):
            m=val[2]
        return m