1037. Unpack Nested Lists

Medium3.5 points estimatedStack Depth-First Search Iterator Design 3 hints

A document exporter receives items, a list whose entries are either integers or further lists of the same kind, nested to any depth. Downstream code wants to read the integers one at a time in left-to-right order, as if the structure had been flattened, but copying everything into a flat array up front is wasteful.

Implement the class NestedUnpacker. NestedUnpacker(items) prepares the unpacker. next() returns the next integer in flattened order; it is only called when one remains. hasNext() reports whether any integer remains and may be called repeatedly without consuming anything. Empty lists contribute nothing.

Each call should run in amortized O(1) time using O(d) extra space, where d is the nesting depth.

Example 1

Input:: operations = ["NestedUnpacker","next","next","hasNext","next","hasNext"]arguments = [[[4,[[5],6],[]]],[],[],[],[],[]]
Output:: [null,4,5,true,6,false]
Explanation:: The integers come out as 4, 5, 6 in order; after 6 is taken only an empty list remains, so the last hasNext is false.

Example 2

Input:: operations = ["NestedUnpacker","hasNext"]arguments = [[[[],[[]]]],[]]
Output:: [null,false]
Explanation:: Every list is empty, so no integer is available and hasNext is false.

Example 3

Input:: operations = ["NestedUnpacker","next","next","next","hasNext"]arguments = [[[[-1,[-2]],3]],[],[],[],[]]
Output:: [null,-1,-2,3,false]
Explanation:: Flattened order is -1, -2, 3, and after reading all three nothing remains.

Constraints

The total number of integers and lists is at most 10⁵.

The nesting depth is at most 100.

-10⁹ ≤ each integer ≤ 10⁹.

At most 2 * 10⁵ calls are made, and next is only called when an integer remains.

How this problem is judged

Answers: Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Input: Each case is an operation log. operations names the class first and then each method call; arguments holds the arguments for each, in the same order. Your answer is one list with a result per operation - null for the constructor and for methods that return nothing.

Expected complexity

Time: O(1) amortized per call
Space: O(d)

What the author was aiming for. Your own solution is not measured against it.

Were you asked this in an interview? Say where, anonymously.

CodeStarter code

Loading the editor…

operations =arguments =

operations names the class, then each method to call; arguments holds one list of arguments per operation, in the same order.