Sponsored
Sponsored
This approach utilizes recursion to flatten the nested list. The idea is to traverse each element in the nested list. If the element is an integer, it gets added to a result list. If it's a list, the function calls itself recursively to add its flattened elements to the result list.
Time Complexity: O(N), where N is the total number of integers in the nested list. Space Complexity: O(N) for the flattened list storage.
1class NestedIterator:
2 def __init__(self, nestedList):
3 self.flatList = []
4 self.index = -1
5 self.flatten(nestedList)
6
7 def flatten(self, nestedList):
8 for element in nestedList:
9 if element.isInteger():
10 self.flatList.append(element.getInteger())
11 else:
12 self.flatten(element.getList())
13
14 def next(self):
15 self.index += 1
16 return self.flatList[self.index]
17
18 def hasNext(self):
19 return self.index + 1 < len(self.flatList)The constructor initializes the object with a flattened list and an iterator index. The `flatten` method is a helper function that recursively adds elements to `flatList`. The `next` method returns the next element from `flatList`, while `hasNext` checks the bounds.
This approach uses a stack to iterate over the nested list in a depth-first manner. This helps simulate recursive behavior iteratively, thus allowing the use of iterator pattern directly without full pre-flattening.
Time Complexity: Amortized O(1) per call for `next` and `hasNext` due to efficient stack management. Space Complexity: O(N), where N is the total number of integers stored in the stack during traversal.
1public class NestedIterator {
2 private Stack<NestedInteger> stack = new Stack<NestedInteger>();
3
4 public NestedIterator(IList<NestedInteger> nestedList) {
5 Flatten(nestedList);
}
private void Flatten(IList<NestedInteger> nestedList) {
for (int i = nestedList.Count - 1; i >= 0; i--) {
stack.Push(nestedList[i]);
}
}
public bool HasNext() {
while (stack.Count > 0) {
NestedInteger top = stack.Pop();
if (top.IsInteger()) {
stack.Push(top);
return true;
}
Flatten(top.GetList());
}
return false;
}
public int Next() {
return stack.Pop().GetInteger();
}
}Similar to the JavaScript solution, the C# code uses a stack to flatten the list iteratively. By pre-loading the stack in reverse order, we ensure correct traversal order. `HasNext` prepares the stack until the next integer is on top.