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

Examples

Example 1:

Input: v1 = [1,2], v2 = [3,4,5,6]
Output: [1,3,2,4,5,6]
Explanation: By calling next repeatedly until hasNext returns false, 
             the order of elements returned by next should be: [1,3,2,4,5,6].

Example 2:

Input: v1 = [1], v2 = []
Output: [1]

Example 3:

Input: v1 = [], v2 = [1]
Output: [1]

Constraints

  • 0 <= v1.length, v2.length <= 1000
  • 1 <= v1.length + v2.length <= 2000
  • -2^31 <= v1[i], v2[i] <= 2^31 - 1

Thinking Process

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

  • Identify required operations and their frequency (get/put/insert).
  • Combine data structures: hash map + list, heap + map, trie + DFS.
  • Amortized O(1) often needs lazy cleanup or doubly-linked lists.
Design pattern API hash + list compose data structures for operations

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Hash map + list (this problem) O(1) avg O(n) LRU cache pattern
Heap + hash map O(log n) O(n) LFU, time-based store
Trie (prefix tree) O(m) O(nm) Word search, autocomplete
Deque / circular buffer O(1) O(n) Queue with fixed capacity

Solution

Time Complexity: O(1) for next() and hasNext()
Space Complexity: O(n) where n is the total number of elements

This approach uses pointers to track the current vector and element position, cycling through vectors in a zigzag pattern.

class ZigzagIterator:
list[list[int>> cache
pVec = 0, pElem = 0
totalNum = 0, outputCount = 0
ZigzagIterator(list[int> v1, list[int> v2) :
cache.append(v1)
cache.append(v2)
for vec in cache:
    totalNum += len(vec)
def next(self):
    iterNum = 0
    while iterNum < len(cache):
        list[int> currVec = cache[pVec]
        if pElem < len(currVec):
            ret = currVec[pElem]
            outputCount += 1
            pVec = (pVec + 1) % len(cache)
            if pVec == 0:
                pElem += 1
            return ret
        iterNum += 1
        pVec = (pVec + 1) % len(cache)
        if pVec == 0:
            pElem += 1
    throw runtime_error("No more elements")
def hasNext(self):
    return outputCount < totalNum
/
 Your ZigzagIterator object will be instantiated and called as such:
 ZigzagIterator i(v1, v2)
 while i.hasNext()) cout << i.next(:
/

Solution Explanation

Approach: Hash map + list (this problem)

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

How the code works:

  • Identify required operations and their frequency (get/put/insert).
  • Combine data structures: hash map + list, heap + map, trie + DFS.
  • Amortized O(1) often needs lazy cleanup or doubly-linked lists.

Walkthrough — input v1 = [1,2], v2 = [3,4,5,6], expected output [1,3,2,4,5,6]:

By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,3,2,4,5,6].

How Solution 1 Works

  1. Initialization: Store both vectors in cache and calculate total number of elements
  2. Pointer Management:
    • pVec: Current vector index (0 or 1)
    • pElem: Current element index within the vector
  3. Zigzag Pattern:
    • Cycle through vectors: pVec = (pVec + 1) % cache.size()
    • When we complete a full cycle (pVec == 0), increment pElem
  4. Skip Empty Vectors: If current vector is exhausted, skip to next vector
  5. Termination: Track outputCount to know when all elements are returned

    Example Walkthrough

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

Solution 1 (Pointer-Based):

Initial: pVec=0, pElem=0, outputCount=0

next(): pVec=0, pElem=0 → return 1, pVec=1, outputCount=1
next(): pVec=1, pElem=0 → return 3, pVec=0, pElem=1, outputCount=2
next(): pVec=0, pElem=1 → return 2, pVec=1, outputCount=3
next(): pVec=1, pElem=1 → return 4, pVec=0, pElem=2, outputCount=4
next(): pVec=0, pElem=2 → skip (out of bounds), pVec=1, pElem=2
next(): pVec=1, pElem=2 → return 5, pVec=0, pElem=3, outputCount=5
next(): pVec=0, pElem=3 → skip, pVec=1, pElem=3
next(): pVec=1, pElem=3 → return 6, outputCount=6

Result: [1,3,2,4,5,6]

Solution 2 (Queue-Based):

Initial: q = [(0,0), (1,0)]

next(): pop (0,0) → return 1, push (0,1) → q = [(1,0), (0,1)]
next(): pop (1,0) → return 3, push (1,1) → q = [(0,1), (1,1)]
next(): pop (0,1) → return 2, push (0,2) → q = [(1,1), (0,2)]
next(): pop (1,1) → return 4, push (1,2) → q = [(0,2), (1,2)]
next(): pop (0,2) → return (skip, out of bounds) → q = [(1,2)]
next(): pop (1,2) → return 5, push (1,3) → q = [(1,3)]
next(): pop (1,3) → return 6 → q = []

Result: [1,3,2,4,5,6]

Edge Cases

  1. Empty vectors: One or both vectors can be empty
  2. Different lengths: Vectors can have different lengths
  3. Single element: One vector has only one element
  4. All elements from one vector: One vector exhausted before the other

Extending to K Vectors

The queue-based approach easily extends to handle k vectors:

class ZigzagIterator:
list[list[int>> cache
deque[pair<int, int>> q
ZigzagIterator(list[int> v1, list[int> v2) :
cache.append(v1)
cache.append(v2)
for(i = 0 i < (int)len(cache) i += 1) :
if not cache[i].empty():
    q.push(:i, 0)
def next(self):
    if not hasNext():
        throw runtime_error("No more elements")
    [vec_index, elem_index] = q[0]
    q.pop()
    next_elem_index = elem_index + 1
    if next_elem_index < cache[vec_index].__len__():
        q.push(:vec_index, next_elem_index)
    return cache[vec_index][elem_index]
def hasNext(self):
    return not not q
/
 Your ZigzagIterator object will be instantiated and called as such:
 ZigzagIterator i(v1, v2)
 while i.hasNext()) cout << i.next(:
/

Key Takeaways

  • Identify required operations and their frequency (get/put/insert).
  • Combine data structures: hash map + list, heap + map, trie + DFS.
  • Amortized O(1) often needs lazy cleanup or doubly-linked lists.

References

Common Mistakes

  • Skipping edge cases (empty input, single element, boundaries).
  • Off-by-one errors in loops and index ranges.
  • Forgetting to handle the case when no valid answer exists.

Pattern Recognition

This problem demonstrates the “Iterator Design Pattern”:

1. Encapsulate traversal logic in a class
2. Provide hasNext() to check availability
3. Provide next() to retrieve elements
4. Handle edge cases (empty vectors, different lengths)
5. Support extension to multiple data sources

Similar patterns:

  • Iterator for complex data structures
  • Lazy evaluation
  • Stream processing