284. Peeking Iterator
Model: qwen3.5:9b
Topics: Design
FAANG asked: 1
Acceptance rate: 50.9%
Problem Breakdown
We need to implement a wrapper class that behaves like an iterator over a given list of integers. The core requirement is adding peek() functionality: looking at the next element without consuming it from the sequence state.
Inputs: An integer array (nums) and method calls (next, hasNext, peek).
Outputs: Integer values for elements, boolean for existence check.
Implicit Constraints & Edge Cases:
- The underlying data is consumed linearly; we must track position accurately.
- “Valid calls” constraint simplifies error handling (we don’t need to handle peeking on an empty iterator), but
hasNextlogic remains critical to prevent out-of-bounds access in the implementation flow. - We cannot modify the input array structure, only our internal state pointer.
Intuition
The standard Iterator pattern maintains a current position and consumes elements sequentially. The challenge is that peek() requires knowledge of the next element without advancing the cursor.
A brute-force approach might involve re-scanning from the start or maintaining multiple pointers, which degrades to O(N) time per operation—unacceptable for an iterator interface (expecting amortized O(1)).
The key insight is state management via a single index. Since we have direct access to the underlying array in Python (nums), we can store it and maintain an integer pointer _index.
next()returns current value at_index, then increments.peek()simply reads from_indexwithout incrementing.hasNext()checks if_index < len(nums).
Follow-up (Generic Types): To extend this to all types, we would use Type Hints (Iterator[T]) in Python rather than hardcoding integers. The logic remains identical; only the storage container changes from a list of ints to a generic iterable or typed buffer. Note that unlike Java/C#, Python type hints are erased at runtime and do not enforce strict generics behavior without external libraries like typing.
Approach
- Initialization: Store reference to
nums(or an iterator object if wrapping) and initialize_index = 0. - Peek Logic: Check bounds implicitly via constraints, return value at current index. Do not increment pointer.
- Next Logic: Retrieve value at current index, then increment
_index. Return the retrieved value. - Has Next Logic: Simple comparison between
_indexand array length.
This ensures all operations are O(1) time complexity with minimal overhead beyond storing the input reference.
Complexity Analysis
- Time Complexity: for
next(),peek(), andhasNext()because they only involve pointer arithmetic or direct memory access (array indexing). - Space Complexity: . We store a reference to the input array within our class instance. While we do not allocate new space for elements, holding the list structure itself scales with N. If strictly counting auxiliary storage beyond what was provided by the caller’s stack frame:
- We hold an index ().
- The
numsreference points to existing data but requires memory footprint within our object context for random access capability required bypeek().
Solution
class PeekingIterator:
def __init__(self, nums):
"""Initialize object with given integer array."""
self.nums = nums
self.index = 0
def peek(self) -> int:
"""Return next element without moving pointer. Valid calls guaranteed."""
return self.nums[self.index]
def next(self) -> int:
"""Returns the next element and moves the pointer to the next element."""
val = self.nums[self.index]
self.index += 1
return val
def hasNext(self) -> bool:
"""Return true if there are still elements in the array."""
return self.index < len(self.nums)
# Example usage matching problem description logic (not part of class definition):
# iterator = PeekingIterator([1, 2, 3])
# print(iterator.next()) # Output: 1
# print(iterator.peek()) # Output: 2
Edge Cases Handled
- Empty Array: Constraints state
nums.length >= 1, so initialization is safe. However, logic relies on_index < len(nums)which correctly returns False if array were empty or exhausted. - Exhausted Iterator: When all elements are consumed (
_index == len),hasNext()returnsFalse. Subsequent calls tonext()orpeek()would be invalid per constraints, but the implementation relies on_indexbounds which prevents index errors if logic is followed correctly (though valid call constraint ensures we don’t access out of bounds). - Single Element: Works seamlessly; pointer moves after first
next(), subsequent checks return False.