Practice/LinkedIn/Leetcode 341. Flatten Nested List Iterator

Leetcode 341. Flatten Nested List Iterator

CodingMust

Problem

You are given a nested list where each element is either an integer or another list that may contain integers or further nested lists. Your task is to design an iterator that can traverse all the integers in this nested structure in a flattened manner.

The iterator must support two operations:

• next(): Returns the next integer in the flattened sequence
• hasNext(): Returns true if there are more integers remaining, false otherwise

The elements should be traversed in depth-first order from left to right. For example, given the structure [[1,1],2,[1,1]], the iterator should return the integers in this order: 1, 1, 2, 1, 1.

You are provided with a NestedInteger interface that represents either a single integer or a nested list:

• isInteger(): Returns true if this object holds a single integer rather than a nested list
• getInteger(): Returns the single integer (only valid if isInteger() returns true)
• getList(): Returns the nested list (only valid if isInteger() returns false)

Requirements

1. Implement the NestedIterator class constructor that accepts a list of NestedInteger objects
2. Implement next() to return the next integer in the flattened sequence
3. Implement hasNext() to check if there are more integers to iterate
4. The iterator should handle arbitrarily deep nesting levels
5. Empty nested lists should be skipped gracefully

Constraints

• The total number of integers in the nested list is in the range [0, 10000]
• The nesting depth will not exceed 50 levels
• next() will only be called when hasNext() returns true
• You may assume the input is well-formed

Examples

Example 1:

Input: nestedList = [[1,1],2,[1,1]] Operations: hasNext(), next(), next(), hasNext(), next(), hasNext(), next(), hasNext(), next(), hasNext() Output: [true, 1, 1, true, 2, true, 1, true, 1, false] Explanation: The iterator flattens the nested structure and returns each integer in order

Example 2:

Input: nestedList = [1,[4,[6]]] Operations: hasNext(), next(), next(), next(), hasNext() Output: [true, 1, 4, 6, false] Explanation: The deeply nested structure is traversed depth-first

Example 3:

Input: nestedList = [[[]]] Operations: hasNext() Output: [false] Explanation: The nested list contains no integers