If a is a List[List[int]] representing a n✕n matrix, what is the time- and space-complexity of a = zip(*a[::-1])?
My thoughts
- Time-complexity has to be at least O(n^2) because we touch n^2 elements. I guess that every element is touched exactly twice (reversing/flipping with
a[::-1]and transposing withzip(*reversed)) list(zip(*a[::-1]))returns a copy, so the space-complexity would be at least n^2. But zip returns an iterator, hence I'm not sure.- I'm especially uncertain about the space complexity, because I read that
zip(*inner)unpacks the inner iterables (source). My guess is that it stores additionally to the input O(n) for keeping pointers for the n inner "unpacked" iterators. But I'm very uncertain about that.
