Python O(1) space solutions


  • 20

    Solution 1

    With a list of remaining downcounter + iterator pairs:

    class ZigzagIterator(object):
    
        def __init__(self, v1, v2):
            self.data = [(len(v), iter(v)) for v in (v1, v2) if v]
    
        def next(self):
            len, iter = self.data.pop(0)
            if len > 1:
                self.data.append((len-1, iter))
            return next(iter)
    
        def hasNext(self):
            return bool(self.data)
    

    Solution 2

    With a generator expression and a down counter:

    class ZigzagIterator(object):
    
        def __init__(self, v1, v2):
            self.vals = (v[i] for i in itertools.count() for v in (v1, v2) if i < len(v))
            self.n = len(v1) + len(v2)
    
        def next(self):
            self.n -= 1
            return next(self.vals)
    
        def hasNext(self):
            return self.n > 0
    

    Solution 3

    With a generator function and a down counter:

    class ZigzagIterator(object):
    
        def __init__(self, v1, v2):
            def vals():
                for i in itertools.count():
                    for v in v1, v2:
                        if i < len(v):
                            yield v[i]
            self.vals = vals()
            self.n = len(v1) + len(v2)
    
        def next(self):
            self.n -= 1
            return next(self.vals)
    
        def hasNext(self):
            return self.n > 0

  • 0
    T

    which one do you like the most?


  • 0

    The second solution is really amazing! In the __init__ method, self.vals has already stored the values in a zigzagging order; the first time I see the usage of (i for i in ...), really cool~


  • 0
    This post is deleted!

  • 1

    @tyr034 I'm very undecided, that's why I posted them all :-)
    I'm not fully happy with any of them, but that's probably because I'm writing a Java-style iterator in Python. I'm not sure there's a really Pythonic way to do that.

    @jianchao.li.fighter Actually, the values aren't already "stored" in zigzag order. It's not a list expression or so, which would indeed precompute and store it all. But I think that's not a real iterator. A real iterator shouldn't copy the data. What I actually use there is a generator expression, which gives me a generator object, which computes elements on the fly on demand using the original data sources.
    If I did want to precompute and store the data, I also wouldn't need the extra n and it would look something like this:

    class ZigzagIterator(object):
    
        def __init__(self, v1, v2):
            self.vals = [x
                         for v in itertools.izip_longest(v1, v2)
                         for x in v
                         if x is not None][::-1]
    
        def next(self):
            return self.vals.pop()
    
        def hasNext(self):
            return bool(self.vals)
    

  • 0

    Hi, Stefan. Well, I should say sorry for my inaccuracies in the words. In fact I realize that it is a generator object but I am just too used to treat it as a list... Your original code is excellent!

    BTW, I learn a new built-in function izip_longest from your above code. Wow, how come this method has such a name? I almost cannot guess what it does at the first glance :-)


  • 2

    Found a cool little trick, instead of writing my own next function wrapping the list's pop, I can just directly use pop as next :-)

    class ZigzagIterator(object):
    
        def __init__(self, v1, v2):
            self.vals = [x
                         for v in itertools.izip_longest(v1, v2)
                         for x in v
                         if x is not None][::-1]
            self.next = self.vals.pop
    
        def hasNext(self):
            return bool(self.vals)
    

  • 0

    Haha, Stefan, your code becomes shorter :-)


  • 1

    Shorter? Ok :-)

    class ZigzagIterator(object):
      def __init__(self, v1, v2):
        v = [x for v in itertools.izip_longest(v1, v2) for x in v if x!=None][::-1]
        self.next = v.pop
        self.hasNext = lambda: bool(v)
    

  • 0

    Haha, nice usage of lambda :-) Great!


  • 0
    S

    Compatible with more vectors: (not sure if it's efficient...)

    class ZigzagIterator(object):
    
        def __init__(self, v1, v2):
            self.queue = [vec for vec in (v1, v2) if vec]
            
    
        def next(self):
            v = self.queue.pop(0)
            ans = v.pop(0)
            if v:
                self.queue.append(v)
            return ans
                
    
        def hasNext(self):
            return len(self.queue) != 0

  • 1

    It's pretty inefficient, as v.pop(0) takes linear time and v can be large.


  • 0
    K

    For Solution 2, will self.vals = (v[i] for i in xrange(max(len(v1), len(v2))) for v in (v1, v2) if i < len(v)) be faster?


  • 0

    @kitt I doubt it makes a significant difference, and I just did some tests where I couldn't tell a difference. Have you tested it yourself? Or do you have some reason to think it could be better?


  • 0
    K

    My test shows it's slightly faster (almost negligible). I was thinking built-in function max and len may be faster than module itertools, but I'm not sure.


  • 0

    How come these are O(1) space? You save data on self.data or self.vals.


  • 0

    @jedihy Those are only O(1) large. What do you think the space complexity is?


  • 0
    X

    Hello Stefan,
    Just to confirm with you that your second solution uses O(1) space and time, right?


  • 0
    X

    @jedihy In python, generator object only stores pointers which come from "imaginary" for loops, therefore, I guess there is no extra N space needed.


  • 0

    @xueguang All three solutions use O(1) space and time.


Log in to reply
 

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