0% completed
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
andv2
) 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, returnfalse
.
- Check if the queue is empty. If it is not empty, return
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
andv2
. -
First Call to
next()
:- The
next()
method dequeues the iterator forv1
(which points to1
). - The value
1
is returned. - Since there are more elements in
v1
, the iterator is re-enqueued.
- The
-
Second Call to
next()
:- The
next()
method dequeues the iterator forv2
(which points to3
). - The value
3
is returned. - Since there are more elements in
v2
, the iterator is re-enqueued.
- The
-
Subsequent Calls to
next()
:- The process continues, alternating between
v1
andv2
, returning2
,4
,5
, and6
in sequence. - After returning
6
, the iterator forv2
is not re-enqueued because it has no more elements.
- The process continues, alternating between
-
Call to
hasNext()
:- The
hasNext()
method checks if the queue is empty. - Since all iterators have been exhausted, it returns
false
.
- The
Code
Here is how we can implement this algorithm:
Complexity Analysis
Time Complexity
-
Solution()
Constructor:
The constructor initializes a queue and adds iterators for non-empty lists (v1
andv2
). Since it only processes a fixed number of lists (two in this case), the time complexity is O(1). -
next()
Method:
Thenext()
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.
.....
.....
.....
Table of Contents
Contents are not accessible
Contents are not accessible
Contents are not accessible
Contents are not accessible
Contents are not accessible