Question: https://leetcode.com/problems/longest-consecutive-sequence/

For this problem I tried the following approach:

1. create a dictionary for keeping sequences and a sequence counter.
2. loop through the list
3. check if the dictionary has sequences or not.
   1. if it does then for all the sequences check
      1. if the current num fits in any.
         1. if it does add it to that sequence.
         2. if it doesn’t create a new sequence
   2. if the dictionary is empty add a new sequence to it.

class Solution:
    def check_seq(self, value, n):
        if n+1 == value:
            self.sequences[self.seq_counter] = n
        elif n-1 == value:
            self.sequences[self.seq_counter] = n
        else:
            self.seq_counter += 1
            self.sequences[self.seq_counter] = [n]

    def longestConsecutive(self, nums):
        self.seq_counter = 1
        self.sequences = {}
        for n in nums:
            if self.sequences:
                for value in self.sequences.values():
                    for individual_num in value:
                        self.check_seq(individual_num, n)
            else:
                self.sequences[self.seq_counter] = [n]
                
s = Solution()
s.longestConsecutive([100,4,200,1,3,2])

This seemed like a great approach until:

for value in self.sequences.values():
RuntimeError: dictionary changed size during iteration

I didn’t knew that dictionaries can not change there values at runtime. They could in Python 2 but Not in Python 3.

Now the fait seemed impossible.

but then I peeked into the topic names. Union Find was one name in it. and the word union clicked me that I might do something with sets. They surely can be updated in some way. Also, it resonated with trees. However, I don’t know anything about implementation of trees. So, let’s see where it goes.

I found another loop whole in the approach I was working with earlier. So, its definitely the most stupid solutions.

I would revisit this question when I study trees. For now, as I read in discussion this is accepting sorting solutions.

And with that I think that I need to put much more work on array. I’ll be solving many more easy problems in order to qualify the constraints provided.

I did solve it this much but couldn’t pass test cases like [0, 0] I think they should mention before hand if duplicates are to be counted as one.

class Solution:
    def longestConsecutive(self, nums):
        self.seq_counter = 1
        self.sequences = {1:[]}
        if (len(nums) == 1):
            return 1
        nums.sort()
        for i in range(len(nums)):
            if (i+1) < len(nums):
                if(nums[i] != nums[i+1]):
                    if nums[i]+1 == nums[i+1] or nums[i-1]+1 == nums[i]:
                        if not self.sequences:
                            self.sequences[self.seq_counter] = [nums[i]]
                            
                        else:
                            self.sequences[self.seq_counter].append(nums[i])
                    else:
                        self.seq_counter += 1
                        self.sequences[self.seq_counter] = [nums[i]]
            else:
                if(nums[i] != nums[i-1]):
                    if nums[i-1]+1 == nums[i]:
                        if not self.sequences:
                            self.sequences[self.seq_counter] = [nums[i]]     
                        else:
                            self.sequences[self.seq_counter].append(nums[i])
                    else:
                        self.seq_counter += 1
                        self.sequences[self.seq_counter] = [nums[i]]

        maximum = len(self.sequences[1])
        for values in self.sequences.values():
            if len(values) > maximum:
                maximum = len(values)
        return maximum

Next, I gave up and checked out the solution.

So, damm easy it was. nothing just using a max length track that’s it.

1. create a set of the provided list. This will avoid duplicates easily.
2. run a for loop on the set.