Flatten Nested List Iterator

Explanation & Solution

Description

You are given a nested list of integers nestedList. Each element is either an integer or a list whose elements may also be integers or other lists. Implement an iterator to flatten it.

Implement the NestedIterator class:

NestedIterator(nestedList) Initializes the iterator with the nested list nestedList.
next() Returns the next integer in the nested list.
hasNext() Returns true if there are still some integers in the nested list and false otherwise.

Each NestedInteger has the following interface:

isInteger() returns true if this NestedInteger holds a single integer.
getInteger() returns the single integer this NestedInteger holds (if it holds a single integer).
getList() returns the nested list this NestedInteger holds (if it holds a nested list).

Input: nestedList = [[1,1],2,[1,1]]

Output:[1,1,2,1,1]

Explanation: By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,1,2,1,1].

Constraints

1 <= nestedList.length <= 500
The values of the integers in the nested list is in the range [-10^6, 10^6]

Approach

Stacks pattern

1. Stack Initialization

Push all elements of nestedList onto the stack in reverse order
This ensures the first element is on top of the stack

2. hasNext() — Flatten on Demand

While the stack is non-empty:
If the top is an integer, return true
If the top is a list, pop it and push its children in reverse order
If the stack becomes empty, return false

3. next() — Return the Top Integer

Since hasNext() guarantees the top is an integer, simply pop and return it

Key Insight

The stack enables lazy flattening — we only unpack nested lists when needed
Pushing children in reverse order maintains the correct left-to-right traversal
This approach uses O(d) space where d is the maximum nesting depth (in the worst case O(n))
The hasNext() method does the heavy lifting, ensuring next() is always O(1)

Solution Code

Remove K Digits