# Python O(1) space solutions

• 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

• which one do you like the most?

• 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~

• This post is deleted!

• @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)

• 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 :-)

• 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)

• Haha, Stefan, your code becomes shorter :-)

• 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)

• Haha, nice usage of lambda :-) Great!

• 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

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

• 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?

• @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?

• 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.

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

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

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

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

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

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