Finding MEX of a changing set

March 7, 2023

I am trying to create a method add that adds elements x to the set one by one and returns MEX (=minimum non-negative number not in the set) of the list at each point.

class Mex:
    def __init__(self):
        self.mex = set()

    def add(self, x):
        self.mex.add(x)
        mex = 0
        while mex in self.mex:
            mex += 1
        return mex

This is not efficient enough and it’s probably because the set changes each time. I have also tried the following but the problem is the same

    def add(self,x):   
         self.mex.add(x)
         for i in range(len(self.mex)):
             if i not in self.mex:
                 return i
        
         return len(self.mex)

Tips?

>Solution :

Don’t always start from 0 again, remember where you were.

class Mex:
    def __init__(self):
        self.added = set()
        self.mex = 0

    def add(self, x):
        self.added.add(x)
        while self.mex in self.added:
            self.mex += 1
        return self.mex