Flatten Nested List Iterator

Medium Design Data Structures Stack Original on LeetCode

Flatten Nested List Iterator is a medium design data structures problem solved with the stack pattern. The best approach, optimal (lazy stack of cursors), runs in O(1) amortized per call time and O(D) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (flatten everything up front) up.

Problem

You are given a nested list of integers nestedList. Every element is either an integer or another list, whose elements can again be integers or lists, to any depth.

Implement the NestedIterator class, which walks through all the integers in reading order (left to right, going inside each sub-list where it appears):

  • NestedIterator(nestedList) creates the iterator over the given nested list.
  • next() returns the next integer.
  • hasNext() returns true if there are integers left, false otherwise.

You may only inspect the structure through the NestedInteger interface: isInteger() tells you whether the element holds a single integer, getInteger() returns that integer, and getList() returns the element’s list. The judge creates the iterator and keeps calling hasNext() and next(); your output is correct if the sequence of returned integers equals the flattened list.

Examples

Example 1

Input
nestedList = [[4, 1], 6, [[2]]]
Output
[4, 1, 6, 2]
Why
Calling hasNext() and next() until hasNext() is false returns the integers in reading order: 4, 1, 6, 2.

Example 2

Input
nestedList = [7, [], [[-3, [8]]], []]
Output
[7, -3, 8]
Why
Empty lists contribute nothing; the deeply nested -3 and 8 still come out in order.

Example 3

Input
nestedList = [[], [[]]]
Output
[]
Why
There are no integers at all, so the very first hasNext() returns false.

Constraints

  • 1 <= nestedList.length <= 500
  • Integers are in the range [-10^6, 10^6].
  • Lists can be nested up to 500 levels deep and may be empty.
  • next() is only called when hasNext() would return true.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (flatten everything up front)O(N) constructor, O(1) next/hasNextO(N)
Optimal (lazy stack of cursors)O(1) amortized per callO(D)

1Brute force (flatten everything up front)

TimeO(N) constructor, O(1) next/hasNextN is the number of integers plus lists. Every element is visited once while flattening; after that each call is a single index operation.
SpaceO(N)The flat copy holds all integers, and the recursion goes as deep as the nesting.

In the constructor, walk the whole structure recursively and copy every integer into one flat list. The iterator is then just an index into that list.

  1. Constructor: call flatten(nestedList), which appends integers and recurses into sub-lists.
  2. hasNext(): return pos < values.size().
  3. next(): return values.get(pos++).
class NestedIterator implements Iterator<Integer> {
    private final List<Integer> values = new ArrayList<>();
    private int pos = 0;

    public NestedIterator(List<NestedInteger> nestedList) {
        flatten(nestedList);
    }

    private void flatten(List<NestedInteger> list) {
        for (NestedInteger ni : list) {
            if (ni.isInteger()) values.add(ni.getInteger());
            else flatten(ni.getList());
        }
    }

    @Override
    public Integer next() {
        return values.get(pos++);
    }

    @Override
    public boolean hasNext() {
        return pos < values.size();
    }
}

2Optimal (lazy stack of cursors)

TimeO(1) amortized per callEach integer and each list is pushed, inspected and popped once over the whole iteration, so the total work is O(N) spread across the N calls.
SpaceO(D)The stack holds one cursor per nesting level, so D is the maximum depth; no copy of the integers is made.

Keep a stack with one cursor (list + index) for every list you are currently inside. hasNext() advances until the top cursor points at an integer: an exhausted cursor is popped, a list element pushes a new cursor for that list. The integer it finds is cached, so repeated hasNext() calls do nothing extra and next() just hands it over. Only the part of the structure that is actually read gets visited.

  1. Constructor: push a cursor at index 0 of nestedList; no cached value.
  2. hasNext(): while nothing is cached and the stack is not empty: if the top cursor is past its list's end, pop it; otherwise take its element and advance the cursor. An integer is cached; a list gets a new cursor pushed.
  3. Return whether a value is cached.
  4. next(): call hasNext(), then return the cached value and clear the cache.
class NestedIterator implements Iterator<Integer> {
    private final Deque<Iterator<NestedInteger>> stack = new ArrayDeque<>();
    private Integer cached = null;

    public NestedIterator(List<NestedInteger> nestedList) {
        stack.push(nestedList.iterator());
    }

    @Override
    public boolean hasNext() {
        while (cached == null && !stack.isEmpty()) {
            Iterator<NestedInteger> top = stack.peek();
            if (!top.hasNext()) {
                stack.pop();
                continue;
            }
            NestedInteger ni = top.next();
            if (ni.isInteger()) cached = ni.getInteger();
            else stack.push(ni.getList().iterator());
        }
        return cached != null;
    }

    @Override
    public Integer next() {
        hasNext();
        Integer v = cached;
        cached = null;
        return v;
    }
}

Edge cases to test

  • Empty inner lists, including lists that contain only empty lists
  • No integers anywhere: hasNext() is false from the start
  • hasNext() called several times in a row without next()
  • next() called without a preceding hasNext()
  • Very deep nesting like [[[[5]]]]

Hints

Hint 1

The simplest correct iterator copies everything into a flat list in the constructor. What does that cost when only a few elements are read?

Hint 2

To be lazy, keep a stack of positions: one cursor per list you are currently inside.

Hint 3

Let hasNext() do the work: keep descending into lists and popping finished ones until the cursor on top points at an integer (or the stack is empty). Then next() just returns it.

FAQ

What is the best time complexity for Flatten Nested List Iterator?

Optimal (lazy stack of cursors) runs in O(1) amortized per call time and O(D) extra space. Each integer and each list is pushed, inspected and popped once over the whole iteration, so the total work is O(N) spread across the N calls.

Which pattern does Flatten Nested List Iterator use?

It is a design data structures problem that uses the stack pattern. Other problems with the same pattern: Min Stack, Design a Stack With Increment Operation, Maximum Frequency Stack.

Is there a brute force solution for Flatten Nested List Iterator?

Yes. Brute force (flatten everything up front) takes O(N) constructor, O(1) next/hasNext time and O(N) space. In the constructor, walk the whole structure recursively and copy every integer into one flat list.

Which edge cases should I test for Flatten Nested List Iterator?

Empty inner lists, including lists that contain only empty lists; No integers anywhere: hasNext() is false from the start; hasNext() called several times in a row without next(); next() called without a preceding hasNext(); Very deep nesting like [[[[5]]]].