Merge Two Sorted Iterators

Problem

Given two sorted iterators, merge them into one iterator.

For example, given these two iterators:

1
2


foo = iter([5, 10, 15])
bar = iter([3, 8, 9])

You should be able to do:

1
2
3
4
5
6
7
8
9


for num in merge_iterators(foo, bar):
    print(num)

# 3
# 5
# 8
# 9
# 10
# 15

Bonus: Make it work without pulling in the contents of the iterators in memory.

Examples

Example 1

1
2
3


Input: iter1 = [5, 10, 15], iter2 = [3, 8, 9]
Output: [3, 5, 8, 9, 10, 15]
Explanation: Merge two sorted iterators maintaining sorted order.

Example 2

1
2
3


Input: iter1 = [1, 3, 5], iter2 = [2, 4, 6]
Output: [1, 2, 3, 4, 5, 6]
Explanation: Perfect interleaving of elements from both iterators.

Example 3

1
2
3


Input: iter1 = [1, 2, 3], iter2 = [4, 5, 6]
Output: [1, 2, 3, 4, 5, 6]
Explanation: First iterator completely exhausted before second.

Example 4

1
2
3


Input: iter1 = [], iter2 = [1, 2, 3]
Output: [1, 2, 3]
Explanation: One iterator is empty, return all elements from non-empty one.

Example 5

1
2
3


Input: iter1 = [1, 1, 2], iter2 = [1, 3, 3]
Output: [1, 1, 1, 2, 3, 3]
Explanation: Handle duplicate values correctly.

Solution

Method 1 - Two-Pointer Merge with Peek Buffering

Intuition

The key insight is to implement a merge operation similar to merge sort, but working with iterators instead of arrays. We need to peek at the next element from each iterator without consuming it, compare them, and yield the smaller one. To achieve this without loading all data into memory, we maintain small buffers that hold the next element from each iterator.

Approach

Initialize Buffers: Create buffers to hold the next element from each iterator
Peek Mechanism: Implement a peek function that fetches the next element if buffer is empty
Comparison Loop:
- Compare buffered elements from both iterators
- Yield the smaller element and refill its buffer
- Continue until both iterators are exhausted
Handle Exhaustion: When one iterator is exhausted, yield all remaining elements from the other
Memory Efficiency: Only keep one element buffered from each iterator at any time

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71


class Solution {
public:
    template<typename Iterator>
    class MergedIterator {
    private:
        Iterator iter1, iter2;
        Iterator end1, end2;
        bool hasNext1, hasNext2;
        typename Iterator::value_type next1, next2;
        
        void advance1() {
            if (iter1 != end1) {
                next1 = *iter1;
                ++iter1;
                hasNext1 = true;
            } else {
                hasNext1 = false;
            }
        }
        
        void advance2() {
            if (iter2 != end2) {
                next2 = *iter2;
                ++iter2;
                hasNext2 = true;
            } else {
                hasNext2 = false;
            }
        }
        
    public:
        MergedIterator(Iterator it1, Iterator e1, Iterator it2, Iterator e2) 
            : iter1(it1), end1(e1), iter2(it2), end2(e2) {
            advance1();
            advance2();
        }
        
        bool hasNext() {
            return hasNext1 || hasNext2;
        }
        
        typename Iterator::value_type next() {
            if (!hasNext1 && !hasNext2) {
                throw runtime_error("No more elements");
            }
            
            typename Iterator::value_type result;
            
            if (!hasNext1) {
                result = next2;
                advance2();
            } else if (!hasNext2) {
                result = next1;
                advance1();
            } else if (next1 <= next2) {
                result = next1;
                advance1();
            } else {
                result = next2;
                advance2();
            }
            
            return result;
        }
    };
    
    template<typename Iterator>
    MergedIterator<Iterator> mergeIterators(Iterator it1, Iterator e1, Iterator it2, Iterator e2) {
        return MergedIterator<Iterator>(it1, e1, it2, e2);
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95


type MergedIterator struct {
    ch1, ch2   <-chan int
    next1, next2 int
    hasNext1, hasNext2 bool
    done1, done2 bool
}

func NewMergedIterator(iter1, iter2 []int) *MergedIterator {
    ch1 := make(chan int, 1)
    ch2 := make(chan int, 1)
    
    go func() {
        defer close(ch1)
        for _, v := range iter1 {
            ch1 <- v
        }
    }()
    
    go func() {
        defer close(ch2)
        for _, v := range iter2 {
            ch2 <- v
        }
    }()
    
    mi := &MergedIterator{ch1: ch1, ch2: ch2}
    mi.advance1()
    mi.advance2()
    return mi
}

func (mi *MergedIterator) advance1() {
    if !mi.done1 {
        val, ok := <-mi.ch1
        if ok {
            mi.next1 = val
            mi.hasNext1 = true
        } else {
            mi.hasNext1 = false
            mi.done1 = true
        }
    }
}

func (mi *MergedIterator) advance2() {
    if !mi.done2 {
        val, ok := <-mi.ch2
        if ok {
            mi.next2 = val
            mi.hasNext2 = true
        } else {
            mi.hasNext2 = false
            mi.done2 = true
        }
    }
}

func (mi *MergedIterator) HasNext() bool {
    return mi.hasNext1 || mi.hasNext2
}

func (mi *MergedIterator) Next() int {
    if !mi.hasNext1 && !mi.hasNext2 {
        panic("No more elements")
    }
    
    var result int
    
    if !mi.hasNext1 {
        result = mi.next2
        mi.advance2()
    } else if !mi.hasNext2 {
        result = mi.next1
        mi.advance1()
    } else if mi.next1 <= mi.next2 {
        result = mi.next1
        mi.advance1()
    } else {
        result = mi.next2
        mi.advance2()
    }
    
    return result
}

func MergeIterators(iter1, iter2 []int) []int {
    mi := NewMergedIterator(iter1, iter2)
    var result []int
    
    for mi.HasNext() {
        result = append(result, mi.Next())
    }
    
    return result
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66


class Solution {
    public static class MergedIterator<T extends Comparable<T>> implements Iterator<T> {
        private Iterator<T> iter1, iter2;
        private T next1, next2;
        private boolean hasNext1, hasNext2;
        
        public MergedIterator(Iterator<T> it1, Iterator<T> it2) {
            this.iter1 = it1;
            this.iter2 = it2;
            advance1();
            advance2();
        }
        
        private void advance1() {
            if (iter1.hasNext()) {
                next1 = iter1.next();
                hasNext1 = true;
            } else {
                hasNext1 = false;
            }
        }
        
        private void advance2() {
            if (iter2.hasNext()) {
                next2 = iter2.next();
                hasNext2 = true;
            } else {
                hasNext2 = false;
            }
        }
        
        @Override
        public boolean hasNext() {
            return hasNext1 || hasNext2;
        }
        
        @Override
        public T next() {
            if (!hasNext()) {
                throw new NoSuchElementException();
            }
            
            T result;
            
            if (!hasNext1) {
                result = next2;
                advance2();
            } else if (!hasNext2) {
                result = next1;
                advance1();
            } else if (next1.compareTo(next2) <= 0) {
                result = next1;
                advance1();
            } else {
                result = next2;
                advance2();
            }
            
            return result;
        }
    }
    
    public <T extends Comparable<T>> MergedIterator<T> mergeIterators(Iterator<T> iter1, Iterator<T> iter2) {
        return new MergedIterator<>(iter1, iter2);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50


class Solution:
    class MergedIterator:
        def __init__(self, iter1: Iterator[int], iter2: Iterator[int]):
            self.iter1 = iter1
            self.iter2 = iter2
            self.next1: Optional[int] = None
            self.next2: Optional[int] = None
            self.hasNext1: bool = False
            self.hasNext2: bool = False
            self._advance1()
            self._advance2()
        
        def _advance1(self) -> None:
            try:
                self.next1 = next(self.iter1)
                self.hasNext1 = True
            except StopIteration:
                self.hasNext1 = False
        
        def _advance2(self) -> None:
            try:
                self.next2 = next(self.iter2)
                self.hasNext2 = True
            except StopIteration:
                self.hasNext2 = False
        
        def __iter__(self) -> 'Solution.MergedIterator':
            return self
        
        def __next__(self) -> int:
            if not self.hasNext1 and not self.hasNext2:
                raise StopIteration
            
            if not self.hasNext1:
                result = self.next2
                self._advance2()
            elif not self.hasNext2:
                result = self.next1
                self._advance1()
            elif self.next1 <= self.next2:
                result = self.next1
                self._advance1()
            else:
                result = self.next2
                self._advance2()
            
            return result
    
    def mergeIterators(self, iter1: Iterator[int], iter2: Iterator[int]) -> Iterator[int]:
        return self.MergedIterator(iter1, iter2)

Complexity

⏰ Time complexity: O(n + m) where n and m are the lengths of the two iterators. Each element is accessed exactly once.
🧺 Space complexity: O(1) additional space as we only buffer one element from each iterator at any time.

Method 2 - Generator-Based Lazy Evaluation

Intuition

We can use generators (or equivalent lazy evaluation mechanisms) to create a more elegant solution that naturally handles the streaming nature of iterators. This approach uses Python’s generator functions or similar constructs in other languages to yield elements on-demand without storing intermediate results.

Approach

Lazy Evaluation: Use generators to process elements only when requested
State Management: Track the current state of both iterators
Exception Handling: Use try-catch to detect iterator exhaustion
Yield on Demand: Generate merged elements one at a time
Memory Optimization: No intermediate storage, pure streaming approach

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86


class Solution {
public:
    template<typename T>
    class LazyMergedIterator {
    private:
        function<optional<T>()> gen1, gen2;
        optional<T> peek1, peek2;
        
        optional<T> getNext1() {
            if (!peek1.has_value()) {
                peek1 = gen1();
            }
            return peek1;
        }
        
        optional<T> getNext2() {
            if (!peek2.has_value()) {
                peek2 = gen2();
            }
            return peek2;
        }
        
        optional<T> consumeNext1() {
            auto val = getNext1();
            peek1.reset();
            return val;
        }
        
        optional<T> consumeNext2() {
            auto val = getNext2();
            peek2.reset();
            return val;
        }
        
    public:
        template<typename Iterator>
        LazyMergedIterator(Iterator it1, Iterator end1, Iterator it2, Iterator end2) {
            gen1 = [it1, end1]() mutable -> optional<T> {
                if (it1 != end1) {
                    return *(it1++);
                }
                return nullopt;
            };
            
            gen2 = [it2, end2]() mutable -> optional<T> {
                if (it2 != end2) {
                    return *(it2++);
                }
                return nullopt;
            };
        }
        
        optional<T> next() {
            auto val1 = getNext1();
            auto val2 = getNext2();
            
            if (!val1.has_value() && !val2.has_value()) {
                return nullopt;
            }
            
            if (!val1.has_value()) {
                return consumeNext2();
            }
            
            if (!val2.has_value()) {
                return consumeNext1();
            }
            
            if (val1.value() <= val2.value()) {
                return consumeNext1();
            } else {
                return consumeNext2();
            }
        }
        
        bool hasNext() {
            return getNext1().has_value() || getNext2().has_value();
        }
    };
    
    template<typename Iterator>
    LazyMergedIterator<typename Iterator::value_type> lazyMerge(
        Iterator it1, Iterator end1, Iterator it2, Iterator end2) {
        return LazyMergedIterator<typename Iterator::value_type>(it1, end1, it2, end2);
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91


func LazyMergeIterators(iter1, iter2 []int) <-chan int {
    result := make(chan int)
    
    go func() {
        defer close(result)
        
        ch1 := make(chan int, 1)
        ch2 := make(chan int, 1)
        done1, done2 := make(chan bool), make(chan bool)
        
        // Start goroutines for each iterator
        go func() {
            defer close(ch1)
            defer close(done1)
            for _, v := range iter1 {
                select {
                case ch1 <- v:
                case <-done1:
                    return
                }
            }
        }()
        
        go func() {
            defer close(ch2)
            defer close(done2)
            for _, v := range iter2 {
                select {
                case ch2 <- v:
                case <-done2:
                    return
                }
            }
        }()
        
        var val1, val2 int
        var ok1, ok2 bool
        var hasVal1, hasVal2 bool
        
        // Get initial values
        select {
        case val1, ok1 = <-ch1:
            hasVal1 = ok1
        case <-done1:
        }
        
        select {
        case val2, ok2 = <-ch2:
            hasVal2 = ok2
        case <-done2:
        }
        
        for hasVal1 || hasVal2 {
            if !hasVal1 {
                result <- val2
                select {
                case val2, ok2 = <-ch2:
                    hasVal2 = ok2
                default:
                    hasVal2 = false
                }
            } else if !hasVal2 {
                result <- val1
                select {
                case val1, ok1 = <-ch1:
                    hasVal1 = ok1
                default:
                    hasVal1 = false
                }
            } else if val1 <= val2 {
                result <- val1
                select {
                case val1, ok1 = <-ch1:
                    hasVal1 = ok1
                default:
                    hasVal1 = false
                }
            } else {
                result <- val2
                select {
                case val2, ok2 = <-ch2:
                    hasVal2 = ok2
                default:
                    hasVal2 = false
                }
            }
        }
    }()
    
    return result
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62


class Solution {
    public static class LazyMergedIterator<T extends Comparable<T>> implements Iterator<T> {
        private Iterator<T> iter1, iter2;
        private T peek1, peek2;
        private boolean hasPeek1, hasPeek2;
        
        public LazyMergedIterator(Iterator<T> it1, Iterator<T> it2) {
            this.iter1 = it1;
            this.iter2 = it2;
            advance();
        }
        
        private void advance() {
            if (!hasPeek1 && iter1.hasNext()) {
                peek1 = iter1.next();
                hasPeek1 = true;
            }
            
            if (!hasPeek2 && iter2.hasNext()) {
                peek2 = iter2.next();
                hasPeek2 = true;
            }
        }
        
        @Override
        public boolean hasNext() {
            advance();
            return hasPeek1 || hasPeek2;
        }
        
        @Override
        public T next() {
            advance();
            
            if (!hasPeek1 && !hasPeek2) {
                throw new NoSuchElementException();
            }
            
            T result;
            
            if (!hasPeek1) {
                result = peek2;
                hasPeek2 = false;
            } else if (!hasPeek2) {
                result = peek1;
                hasPeek1 = false;
            } else if (peek1.compareTo(peek2) <= 0) {
                result = peek1;
                hasPeek1 = false;
            } else {
                result = peek2;
                hasPeek2 = false;
            }
            
            return result;
        }
    }
    
    public <T extends Comparable<T>> Iterator<T> lazyMerge(Iterator<T> iter1, Iterator<T> iter2) {
        return new LazyMergedIterator<>(iter1, iter2);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77


class Solution:
    def mergeIterators(self, iter1: Iterator[int], iter2: Iterator[int]) -> Iterator[int]:
        val1 = val2 = None
        has1 = has2 = False
        
        try:
            val1 = next(iter1)
            has1 = True
        except StopIteration:
            pass
        
        try:
            val2 = next(iter2)
            has2 = True
        except StopIteration:
            pass
        
        while has1 or has2:
            if not has1:
                yield val2
                try:
                    val2 = next(iter2)
                    has2 = True
                except StopIteration:
                    has2 = False
            elif not has2:
                yield val1
                try:
                    val1 = next(iter1)
                    has1 = True
                except StopIteration:
                    has1 = False
            elif val1 <= val2:
                yield val1
                try:
                    val1 = next(iter1)
                    has1 = True
                except StopIteration:
                    has1 = False
            else:
                yield val2
                try:
                    val2 = next(iter2)
                    has2 = True
                except StopIteration:
                    has2 = False
    
    def mergeIteratorsGenerator(self, iter1: Iterator[int], iter2: Iterator[int]) -> Iterator[int]:
        """Alternative implementation using generator approach"""
        
        def peek_iterator(iterator: Iterator[int]) -> Iterator[Tuple[Optional[int], bool]]:
            try:
                while True:
                    yield next(iterator), True
            except StopIteration:
                while True:
                    yield None, False
        
        peek1 = peek_iterator(iter1)
        peek2 = peek_iterator(iter2)
        
        val1, has1 = next(peek1)
        val2, has2 = next(peek2)
        
        while has1 or has2:
            if not has1:
                yield val2
                val2, has2 = next(peek2)
            elif not has2:
                yield val1
                val1, has1 = next(peek1)
            elif val1 <= val2:
                yield val1
                val1, has1 = next(peek1)
            else:
                yield val2
                val2, has2 = next(peek2)

Complexity

⏰ Time complexity: O(n + m) where n and m are the lengths of the iterators. Each element is processed exactly once with lazy evaluation.
🧺 Space complexity: O(1) as we maintain minimal state and use lazy evaluation without storing intermediate results.

Problem#

Examples#

Example 1#

Example 2#

Example 3#

Example 4#

Example 5#

Solution#

Method 1 - Two-Pointer Merge with Peek Buffering#

Intuition#

Approach#

Code#

Complexity#

Method 2 - Generator-Based Lazy Evaluation#

Intuition#

Approach#

Code#

Complexity#

Problem

Examples

Example 1

Example 2

Example 3

Example 4

Example 5

Solution

Method 1 - Two-Pointer Merge with Peek Buffering

Intuition

Approach

Code

Complexity

Method 2 - Generator-Based Lazy Evaluation

Intuition

Approach

Code

Complexity