Leetcode 281. Zigzag Iterator

Problem Explanation:

Given two vectors, the problem asks to develop an iterator to return their elements alternately. The main idea here is to set up an alternation system, in which elements from the first and second vector are interleaved.

For example:

If Input vectors are: v1 = [1,2] v2 = [3,4,5,6]

For the first vector "v1", we pick the first element "1", then for the next vector "v2", we pick the first element "3", Again for "v1", we pick the second element "2", Then for "v2" all the remaining elements will be picked as there are no elements left in "v1". Hence the Output list after applying the Zigzag order would be: [1,3,2,4,5,6]

Let's understand in detail how the provided solution works.

Solution Approach:

The approach here is to use a queue and insert the pairs of iterators into it. For each vector v, we store a pair of its beginning iterator and its end iterator in the queue q. Whenever we call next(), we extract the front of the queue, increment its beginning iterator, and push it back to the queue.

Walkthrough:

For instance, we insert pair(begin(v1), end(v1)) and pair(begin(v2), end(v2)) into q.

When we call next(),

  • We pop the front pair i,e from the queue.
  • Increment i and if i hasn't reached e, we insert i,e back into the queue.
  • We return *i.

Python Solution:

1
2python
3from collections import deque
4
5class ZigzagIterator:
6    def __init__(self, v1, v2):
7        self.data = deque([(v.__iter__(), len(v)) for v in (v1, v2) if v])
8
9    def next(self):
10        v, length = self.data.popleft()
11        if length > 1:
12            self.data.append((v, length-1))
13        return next(v)
14
15    def hasNext(self):
16        return bool(self.data)

Java Solution:

1
2java
3class ZigzagIterator {
4    LinkedList<Iterator> list;
5    public ZigzagIterator(List<Integer> v1, List<Integer> v2) {
6        list = new LinkedList<Iterator>();
7        if(!v1.isEmpty()) list.add(v1.iterator());
8        if(!v2.isEmpty()) list.add(v2.iterator());
9    }
10
11    public int next() {
12        Iterator poll = list.remove();
13        int result = (Integer)poll.next();
14        if(poll.hasNext()) list.add(poll);
15        return result;
16    }
17
18    public boolean hasNext() {
19        return !list.isEmpty();
20    }
21}

JavaScript Solution:

1
2javascript
3class ZigzagIterator {
4    constructor(v1, v2) {
5        this.iterators = [v1[Symbol.iterator](), v2[Symbol.iterator]()];
6        this.values = [this.iterators[0].next(), this.iterators[1].next()];
7    }
8
9    next() {
10        const value = this.values[0] && !this.values[0].done ?
11            this.values.shift() : this.values.pop();
12        if (value && !value.done) {
13            this.values.push(this.iterators[(this.values.length + 1) % 2].next());
14        }
15        return value.value;
16    }
17
18    hasNext() {
19        return this.values.length && !this.values[0].done;
20    }
21}

C++ Solution:

1
2c++
3class ZigzagIterator {
4public:
5    ZigzagIterator(vector<int>& v1, vector<int>& v2) {
6        if (!v1.empty())
7            q.emplace(begin(v1), end(v1));
8        if (!v2.empty())
9            q.emplace(begin(v2), end(v2));
10    }
11
12    int next() {
13        auto [it, endIt] = q.front();
14        q.pop();
15        if (it + 1 != endIt) {
16            q.emplace(it + 1, endIt);
17        }
18        return *it;
19    }
20
21    bool hasNext() {
22        return !q.empty();
23    }
24
25private:
26    queue<pair<vector<int>::iterator, vector<int>::iterator>> q;
27};

C# Solution:

1
2csharp
3class ZigzagIterator {
4    Queue<Tuple<IEnumerator, IEnumerator>> q = new Queue<Tuple<IEnumerator, IEnumerator>>();
5    public ZigzagIterator(List<int> v1, List<int> v2) {
6        if(v1.Count > 0){
7            IEnumerator v1Enumerator = v1.GetEnumerator();
8            v1Enumerator.MoveNext();
9            q.Enqueue(Tuple.Create(v1Enumerator, v1[v1.Count-1].GetEnumerator()));
10        }
11        if(v2.Count > 0){
12            IEnumerator v2Enumerator = v2.GetEnumerator();
13            v2Enumerator.MoveNext();
14            q.Enqueue(Tuple.Create(v2Enumerator, v2[v2.Count-1].GetEnumerator()));
15        }
16    }
17
18    public int Next() {
19        var tuple = q.Dequeue();
20        var result = (int)tuple.Item1.Current;
21        if(tuple.Item1.MoveNext()){
22            q.Enqueue(tuple);
23        }
24        return result;
25    }
26
27    public bool HasNext() {
28        return q.Count > 0;
29    }
30}

In all the solutions, we are making use of an iterator and a queue to maintain the alternative order between the vectors. This same approach will effectively extend to a case where we are given more than two vectors.# Efficiency of the Solution

The above solution is efficient as we are just iterating through the elements once, hence the time complexity would be O(N), where N is the total number of elements in both vectors.

The space complexity is O(1), as we are using a fixed amount of space to store the iterators of both vectors in a queue and a deque.

However, this solution can become inefficient in cases of large datasets, as we are storing the whole dataset in memory. For large datasets, a more memory-efficient solution would be using generator functions or streaming the data in smaller chunks.

Potential Improvements

While the above solution tends to be effective for most cases, there are still some improvements that could be made in certain edge cases.

  1. Lazy Iteration: Instead of processing and storing all the items right at the initiation step, we could lazily iterate over the vectors only when required. This will help when the vectors are extremely large, where storing all elements in memory could be infeasible.

  2. Exception Handling: The Python solution could throw a StopIteration exception if next(v) is called on an empty iterator. So, we can add exception handling to ensure the function behaves correctly even in such cases.

  3. Extending Solution for Multiple Vectors: The given solutions handle only two vectors. However, we can further generalize this solution to zigzag iterate over an arbitrary number of vectors. This can be done by passing the vectors as a list and iterating over them in a circular way.

  4. Maintaining the State of Iterators: Instead of recreating the iterators after each pass, maintaining the state of the iterators could further reduce the memory footprint.

  5. Scalability: For a large number of vectors or for large size vectors, an in-place solution can be implemented which does not require additional space as in the queue based solution.

  6. Simplicity: The solution can be potentially simplified by using built-in language features. For example, in Python, we could potentially make use of the zip and chain functions from the itertools module. This would help in improving the readability and maintainability of the code.

In conclusion, while the given solution is quite efficient for a majority of cases, these potential enhancements could help in handling edge cases more effectively and in making the solution more robust, maintainable, and efficient.


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫