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 {
private:
    vector<vector<int>> cache;
    int pVec = 0, pElem = 0;
    int totalNum = 0, outputCount = 0;

public:
    ZigzagIterator(vector<int>& v1, vector<int>& v2) {
        cache.push_back(v1);
        cache.push_back(v2);
        for(auto& vec: cache) {
            totalNum += vec.size();
        }
    }

    int next() {
        int iterNum = 0;
        while(iterNum < cache.size()) {
            vector<int>& currVec = cache[pVec];
            if(pElem < currVec.size()) {
                int ret = currVec[pElem];
                outputCount++;
                pVec = (pVec + 1) % cache.size();
                if(pVec == 0) {
                    pElem++;
                }
                return ret;
            }
            iterNum++;
            pVec = (pVec + 1) % cache.size();
            if (pVec == 0) {
                pElem++;
            }
        }
        throw runtime_error("No more elements");
    }

    bool hasNext() {
        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 {
private:
    vector<vector<int>> cache;
    queue<pair<int, int>> q;

public:
    ZigzagIterator(vector<vector<int>>& vectors) {
        cache = vectors;
        for(int i = 0; i < (int)cache.size(); i++) {
            if(!cache[i].empty()) {
                q.push({i, 0});
            }
        }
    }

    int next() {
        if (!hasNext()) {
            throw runtime_error("No more elements");
        }
        auto [vec_index, elem_index] = q.front();
        q.pop();
        int next_elem_index = elem_index + 1;
        if(next_elem_index < cache[vec_index].size()) {
            q.push({vec_index, next_elem_index});
        }
        return cache[vec_index][elem_index];
    }

    bool hasNext() {
        return !q.empty();
    }
};

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