Difficulty : Medium Link : April Leetcoding Day 13
You are given a nested list of integers
nestedList. Each element is either an integer or a list whose elements may also be integers or other lists. Implement an iterator to flatten it.
NestedIterator(List<NestedInteger> nestedList)Initialises the iterator with the nested list
int next()Returns the next integer in the nested list.
trueif there are still some integers in the nested list and
Input: nestedList = [[1,1],2,[1,1]] Output: [1,1,2,1,1] Explanation: By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,1,2,1,1].
Input: nestedList = [1,[4,]] Output: [1,4,6] Explanation: By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,4,6].
1 <= nestedList.length <= 500
- The values of the integers in the nested list is in the range
The problem is very Swifty in nature because it you look carefully this is the exact what InteratorProtocol does. If you use a
in loop with an array, set, or any other collection or sequence, you’re already using that type’s iterator (with syntax sugar ofcourse).
Behind the hood, the system creates an iterator using makeIterator() and repeatedly calls next() on the sequence . Since Sequence protocol have an associated type of IteratorProtocol, you never have to worry would how next element would be computed.
The first instinct might be use flatmap() operator directly but you should think about it again. All higher-order operators are defined on Sequence protocol which itself confirm to IteratorProtocol. Here it is the precondition that you have to sort of implement the Iterator functionality itself. So if you are given this problem in an interview, be sure to check with your interviewer first.
The solution is simple, we can have a property for storing list of integers and a index property to maintain the current index. Upon initialisation, we can recursively traverse the nested lists in a depth-first manner. The next thing remains is to simply check if an element is an integer or a nested list. You might be temped to use conditional cast as? Int, however it wouldn’t work. Why? Because NestedInteger is a private class while Int is a struct. You can find that there are utility methods isInteger() and getInteger() which solves our problem. We can create a recursive function to append all integers and recursively calling itself on nested lists.
For getting the next element, we can simple use defer to increment the count after we have returned the current element. HasNext() is pretty straightforward as we only need to compare currentIndex with list count.
Time = O(N) : Where N is the total number of element
Space = O(N)