Solution: Zigzag Iterator

Grokking the Engineering Manager Coding Interview

Ask Author

Back to course home

0% completed

Vote For New Content

Solution: Zigzag Iterator

Table of Contents

Contents are not accessible

Problem Statement

Given two 1d vectors, implement an iterator to return their elements alternately.

Implement the Solution class:

Solution(List<int> v1, List<int> v2) is a constructor.
int next() returns the current element of the iterator and moves the iterator to the next element.
boolean hasNext() returns true if the iterator still has elements, and false otherwise.

Examples

Example 1

Input: V1 = [1,2], v2 = [3,4,5,6]
Expected Output: [1,3,2,4,5,6]
Explanation: The elements will be returned in [1,3,2,4,5,6] order when we make v1.size() + v2.size() number of calls to the next() method.

Example 2

Input: V1 = [1, 2, 3, 4], v2 = [5,6]
Expected Output: [1,5,2,6,3,4]
Explanation: The elements will be returned in [1,5,2,6,3,4] order when we make v1.size() + v2.size() number of calls to the next() method.

Example 3

Input: V1 = [1, 2], v2 = []
Expected Output: [1,2]
Explanation: The elements will be returned in [1, 2] order when we make v1.size() + v2.size() number of calls to the next() method.

Constraints:

0 <= v1.length, v2.length <= 1000
1 <= v1.length + v2.length <= 2000
-2<sup>31</sup> <= v1[i], v2[i] <= 2<sup>31</sup> - 1

Solution

To solve this problem, the solution uses a queue to alternate between elements from two input lists, maintaining the order of appearance. Each non-empty list is converted into an iterator and added to the queue. The next() method retrieves the next element by dequeuing an iterator, extracting its next value, and re-enqueuing the iterator if it still has more elements. This ensures that elements from the two lists are accessed alternately, one by one. The hasNext() method checks if there are any iterators left in the queue, indicating whether more elements are available.

Step-by-Step Algorithm

Initialize the Queue:
- Create a queue to hold iterators for non-empty input lists.
- Convert each non-empty input list (v1 and v2) into an iterator and add them to the queue.
next() Method:
- Dequeue an Iterator: Remove the iterator at the front of the queue.
- Retrieve Next Value: Use the iterator to get the next element in its corresponding list.
- Re-enqueue the Iterator: If the iterator has more elements, add it back to the rear of the queue.
- Return Value: Return the value obtained from the iterator.
hasNext() Method:
- Check if the queue is empty. If it is not empty, return true; otherwise, return false.

Algorithm Walkthrough

input: v1 = [1, 2] and v2 = [3, 4, 5, 6]

Initialization:
- The constructor initializes a queue to hold iterators of the non-empty lists.
- For v1, since it's non-empty, its iterator is added to the queue.
- For v2, its iterator is also added to the queue.
At this point, the queue contains iterators for v1 and v2.
First Call to next():
- The next() method dequeues the iterator for v1 (which points to 1).
- The value 1 is returned.
- Since there are more elements in v1, the iterator is re-enqueued.
Second Call to next():
- The next() method dequeues the iterator for v2 (which points to 3).
- The value 3 is returned.
- Since there are more elements in v2, the iterator is re-enqueued.
Subsequent Calls to next():
- The process continues, alternating between v1 and v2, returning 2, 4, 5, and 6 in sequence.
- After returning 6, the iterator for v2 is not re-enqueued because it has no more elements.
Call to hasNext():
- The hasNext() method checks if the queue is empty.
- Since all iterators have been exhausted, it returns false.

Code

Here is how we can implement this algorithm:

Python3

. . . .

Complexity Analysis

Time Complexity

Solution() Constructor:
The constructor initializes a queue and adds iterators for non-empty lists (v1 and v2). Since it only processes a fixed number of lists (two in this case), the time complexity is $O(1)$ .
next() Method:
The next() method removes an iterator from the queue, retrieves the next element, and re-enqueues the iterator if it has more elements. Each of these operations (remove, add, and check) is performed in constant time, making the overall time complexity $O(1)$ .
hasNext() Method:
This method simply checks whether the queue is empty, which is an $O(1)$ operation.

Space Complexity

Queue Storage:
The queue holds iterators from the non-empty input lists. In this case, it can store up to two iterators, leading to a space complexity of $O(1)$ . If generalized to more lists, the space complexity would be $O(L)$ , where L is the number of non-empty lists.
Iterator Storage:
Each iterator maintains a reference to the list and its current position, which does not depend on the number of elements but is constant per iterator, contributing to $O(1)$ space complexity for each iterator.

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible