How do you solve Peeking Iterator on LeetCode?

Peeking Iterator (LeetCode #284) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(1) space complexity. Key insight: Caching the next element allows peek without moving the iterator.

What is the brute force solution for Peeking Iterator?

The brute force approach for Peeking Iterator is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach involves repeatedly calling the next() method to get the next element. For peek, we would need to call next() and then store the value to return it without moving the iterator's pointer. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Peeking Iterator?

Peeking Iterator uses the following concepts: Array, Design, Iterator. The recommended patterns to study are: Iterator, Caching, State Management.

What are the interview tips for Peeking Iterator?

Clarify the requirements of the iterator methods before coding. Think about edge cases, like calling peek() after reaching the end. Explain your thought process clearly while coding.

What are common mistakes when solving Peeking Iterator?

Not handling the case when peek() is called multiple times. Confusing the behavior of next() and peek() regarding the iterator's position.

#284

Peeking Iterator

Medium

ArrayDesignIteratorIteratorCachingState Management

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(1)

💡

Intuition

Time O(n)Space O(1)

The optimal approach involves caching the next element when peek() is called, allowing us to return it without moving the iterator. This way, we only call next() when necessary.

⚙️

Algorithm

3 steps

1Step 1: Create a class PeekingIterator that takes an existing iterator as input.
2Step 2: Initialize a variable to store the next element and a boolean to track if it has been cached.
3Step 3: In the peek() method, check if the next element is cached; if not, call next() to cache it.

solution.py20 lines

1class PeekingIterator:
2    def __init__(self, iterator):
3        self.iterator = iterator
4        self.cache = None
5        self.has_cache = False
6
7    def next(self):
8        if self.has_cache:
9            self.has_cache = False
10            return self.cache
11        return self.iterator.next()
12
13    def hasNext(self):
14        return self.has_cache or self.iterator.hasNext()
15
16    def peek(self):
17        if not self.has_cache:
18            self.cache = self.iterator.next()
19            self.has_cache = True
20        return self.cache

ℹ

Complexity note: The time complexity is O(n) since each element is processed at most once, and the space complexity is O(1) as we only store one cached element.

1Caching the next element allows peek without moving the iterator.
2Using a boolean flag helps track whether the next element is cached.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.