Tricky 3-lines "fake" iterators, Python + Ruby

  • 1

    I call them "fake" because they copy the source data, which I think real iterators shouldn't do. They should iterate on the fly and on demand over the original data sources.

    I precompute the whole list of zigzagged numbers and reverse it. Then to get the next number, I can just pop it off the end of the list (takes constant time, unlike popping off the front, which takes linear time).


    Instead of defining next as usual, I just directly use the list's pop. And for hasNext, I use a closure. Together, this allows me to not even store the list myself.

    class ZigzagIterator(object):
        def __init__(self, *v):
            v = [x for x in sum(map(None, *v), ()) if x > None][::-1]
   = v.pop
            self.hasNext = lambda: bool(v)

    (x is not None is the proper way, but I want this as short as I can here)

    Using sum can be slow for large inputs (it isn't slow for the OJ's test cases), and this would be faster:

            v = [x for v in map(None, *v) for x in v if x > None][::-1]


    class ZigzagIterator
      def initialize(v1, v2)
        @v = (v1 + [nil] * v2.size).zip(v2).flatten.compact.reverse
      def has_next
      def next

    I'm still a Ruby beginner and don't know whether I could do it like I did in Python. But it's still similar and three times one fairly short line.

    Small variation for initialize:

        @v = (v1 +{nil}).zip(v2).flatten.compact.reverse

  • 0

    Python grammar is really flexible!

  • 0

    Check out the new version, I replaced itertools.izip_longest with map :-)

  • 0

    Ahahahaha, now I also replaced v1, v2 with *v. Forgot that we can do that in Py2 already.

    Also used sum and x > None. Overall this solution might now contain the most "tricks" I have ever used in a solution here.

  • 0

    Oh, now the code has more tricks... In fact, I even know very little about the usage of * in Python.

Log in to reply

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