Flatten Nested List Iterator : Accepted

gouthampradhan · gouthampradhan · commit a4ba73bdfcf8 · 2017-11-30T23:45:00.000+01:00
diff --git a/README.md b/README.md
@@ -83,6 +83,7 @@ My accepted leetcode solutions to some of the common interview problems.
 - [Binary Search Tree Iterator](problems/src/design/BSTIterator.java) (Medium)
 - [Design Search Autocomplete System](problems/src/design/AutocompleteSystem.java) (Hard)
 - [Design Excel Sum Formula](problems/src/design/Excel.java) (Hard)
+- [Flatten Nested List Iterator](problems/src/design/NestedIterator.java) (Medium)
 
 #### [Divide and Conquer](problems/src/divide_and_conquer)
 
diff --git a/problems/src/design/NestedIterator.java b/problems/src/design/NestedIterator.java
@@ -0,0 +1,78 @@
+package design;
+
+import java.util.ArrayList;
+import java.util.Iterator;
+import java.util.List;
+
+/**
+ * Created by gouthamvidyapradhan on 30/11/2017.
+ *
+ * Given a nested list of integers, implement an iterator to flatten it.
+
+ Each element is either an integer, or a list -- whose elements may also be integers or other lists.
+
+ Example 1:
+ Given the list [[1,1],2,[1,1]],
+
+ By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,1,2,1,1].
+
+ Example 2:
+ Given the list [1,[4,[6]]],
+
+ By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,4,6].
+ */
+public class NestedIterator implements Iterator<Integer>{
+
+    private List<Integer> result;
+    private int curr, size;
+
+    // This is the interface that allows for creating nested lists.
+    // You should not implement it, or speculate about its implementation
+    public interface NestedInteger{
+        //@return true if this NestedInteger holds a single integer, rather than a nested list.
+        public boolean isInteger();
+
+        // @return the single integer that this NestedInteger holds, if it holds a single integer
+        // Return null if this NestedInteger holds a nested list
+        public Integer getInteger();
+
+        // @return the nested list that this NestedInteger holds, if it holds a nested list
+        // Return null if this NestedInteger holds a single integer
+        public List<NestedInteger> getList();
+    }
+
+    public NestedIterator(List<NestedInteger> nestedList) {
+        this.result = new ArrayList<>();
+        curr = 0;
+        flatten(result, nestedList);
+        size = result.size();
+    }
+
+    @Override
+    public Integer next() {
+        if(curr < size){
+            return result.get(curr++);
+        }
+        return -1;
+    }
+
+    @Override
+    public boolean hasNext() {
+        return curr < size;
+    }
+
+    public static void main(String[] args) {
+
+    }
+
+    private void flatten(List<Integer> flatList, List<NestedInteger> nestedList){
+        for(NestedInteger n : nestedList){
+            if(n.isInteger()){
+                flatList.add(n.getInteger());
+            } else{
+                flatten(flatList, n.getList());
+            }
+        }
+    }
+
+}
