Design a nested-list iterator
Overview
This question evaluates the ability to implement an efficient iterator over nested lists, testing skills in iterator state management, lazy traversal, explicit stack usage, and algorithmic complexity reasoning.
You are given a nested structure that can contain integers or further lists. Design an iterator over this structure that returns integers in left-to-right order without pre-flattening the entire input. Implement a class NestedIterator with: constructor(nestedList), boolean hasNext(), and int next(). The iterator must use O(d) extra space where d is the maximum nesting depth, and hasNext()/next() should be amortized O( 1). Avoid recursion by using an explicit stack of iterators or indexes. Additionally, implement a recursive pre-flattening approach, compare both methods in time and space complexity, and discuss edge cases such as empty lists, deeply nested empty lists, and integer bounds.