I have an array of integers. I want to find how all unique sets where the difference is 1 and separate them into unique sets.

example input: [3,4,5,8,9,11]

example output: [{3,4,5}, {8,9}, {11}]

What's the simplest way to do this with Python?

CodePudding user response：

Catch the begin of the chain and add all the elements of the chain in a set.

Here is the super simple code for this idea:

def f(arr):
    res = []
    st = set(arr)
    for num in st:
        if num - 1 not in st: #begin of chain
            temp = []
            while num in st:
                temp.append(num)
                num  = 1
            res.append(temp)
    return res
    
print(f([3,4,5,8,9,11]))

Output: [[3, 4, 5], [8, 9], [11]]

Time complexity: O(n)
Space complexity: O(n)

I guess this is the best complexity we can achieve. (Don't mind the variable names in the code