Iterator coding pattern

Overview

What is an Iterator?

A simple iterator is a way of iterating over indexed or finite data structures using for loop as below.

for (const item in items) {
//
}

Iterator have some interesting properties that make them widely useful for not only indexed collections (e.g. Array) and other finite data structures (e.g. LinkedList or HashMap keys), but also for (possibly-infinite) generated data.

An efficientIterator only needs to know how to get the next item. It doesn't need to store the entire data in memory if we don't need the entire data structure. For massive data structures, this is invaluable!

On high level, Iterator class has hasNext() and next() as two methods as below.

class Iterator {
  constructor() {
  }
  bool hasNext(){
  }
  <T> next() {
  }
}

Following is a simple iterator for LinkedList

class LinkedListIterator {
  constructor(head) {
    this.head = head;
    this._current = head;
  }
  hasNext() {
    return !!this._current;
  }
  next() {
    const ans = this._current.value;
    this._current = this._current.next;
    return ans;
  }
}

Following is standard way to use Iterator

Using while loop

Iterator itr = iterator(); // Some way to get the iterator
while(itr.hasNext()) {
   const element = itr.next();
   console.log(element + " ");
}

Using for loop

for(const itr = iterator(); itr.hasNext();) { // Some way to get the iterator
  const element = itr.next();
  console.log(element + " ");
}

Iterator for sequence

An interesting property of Iterators is that they can represent sequences without even using a data structure!

Following is example of range iterator to read number between given min and max range.

class RangeIterator {
  constructor(min, max) {
    this.min = min;
    this.max = max;
    this._current = min;
  }
  hasNext() {
    return this._current < this.max;
  } 
  next() {
    const value = this._current;
    this._current += 1;
    return value;
  }
}

Let’s solve few related problems to understand Iterator in details.

284. Peeking Iterator

https://leetcode.com/problems/peeking-iterator/description/

Design an iterator that supports the peek operation on an existing iterator in addition to the hasNext and the next operations.

Implement the PeekingIterator class:

• PeekingIterator(Iterator<int> nums) Initializes the object with the given integer iterator iterator.
• int next() Returns the next element in the array and moves the pointer to the next element.
• boolean hasNext() Returns true if there are still elements i then the array.
• int peek() Returns the next element in the array without moving the pointer.

Note: Each language may have a different implementation of the constructor and Iterator, but they all support the int next() and boolean hasNext() functions.

Example 1:

Input
["PeekingIterator", "next", "peek", "next", "next", "hasNext"]
[[[1, 2, 3]], [], [], [], [], []]
Output
[null, 1, 2, 2, 3, false]

Approach

1. If we ignore peek() then in both next() and hasNext() should call iterator.next() and iterator.hasNext() .
2. We can initialize peekedValue=null and only populate this value in peek() method by calling iterator.next()
3. Therefore in next() , we will set peekedValue=null and return it so that peek() can populate it again.

Following is code for reference.

/**
 * @param {Iterator} iterator
 */
var PeekingIterator = function (iterator) {
    this.itr = iterator;
    this.peekedValue = null;
};

/**
 * @return {number}
 */
PeekingIterator.prototype.peek = function () {
    // Initialize peeked value if not yet
    if (this.peekedValue == null) {
        this.peekedValue = this.itr.next();
    }
    return this.peekedValue;
};

/**
 * @return {number}
 */
PeekingIterator.prototype.next = function () {
    if (this.peekedValue !== null) {
        const temp = this.peekedValue;
        this.peekedValue = null; // Reset so that peek() will call next()
        return temp;
    }
    return this.itr.next();
};

/**
 * @return {boolean}
 */
PeekingIterator.prototype.hasNext = function () {
    return this.peekedValue != null || this.itr.hasNext();
};

341. Flatten Nested List Iterator

https://leetcode.com/problems/flatten-nested-list-iterator/

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.

Implement the NestedIterator class:

• NestedIterator(List<NestedInteger> nestedList) Initializes the iterator with the nested list nestedList.
• int next() Returns the next integer in the nested list.
• boolean hasNext() Returns true if there are still some integers in the nested list and false otherwise.

Your code will be tested with the following pseudocode:

initialize iterator with nestedList
res = []
while iterator.hasNext()
    append iterator.next() to the end of res
return res

If res matches the expected flattened list, then your code will be judged as correct.

Example 1:

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].

Approach

1. We can leverage iterative version of dfs()
2. We will use inorder version and initialize stack for first order traversal.
3. Insertion of elements in the stack should be in reverse order so that it can pick the first item for porcessing.
4. The ideal way for hasNext() is to simply return true if stack is not empty otherwise false
5. Similarly, the ideal way for next() is to return top of element which is expected to be an integer.
6. To make it happen, in both hasNext() and next() , we will be calling makeStackTopAnInteger() to guaranteed the top is an integer.

Following is code for reference.

/**
 * @constructor
 * @param {NestedInteger[]} nestedList
 */
var NestedIterator = function (nestedList) {
    this._stack = [];
    // Initialize stack in reverse order to match the processing order
    for (let i = nestedList.length - 1; i >= 0; i--) {
        this._stack.push(nestedList[i]);
    }
};


/**
 * @this NestedIterator
 * @returns {boolean}
 */
NestedIterator.prototype.hasNext = function () {
    this._makeStackTopAnInteger();
    return this._stack.length > 0;
};

/**
 * @this NestedIterator
 * @returns {integer}
 */
NestedIterator.prototype.next = function () {
    this._makeStackTopAnInteger();
    return this._stack.pop().getInteger();
};
NestedIterator.prototype._makeStackTopAnInteger = function () {
    // Keep unpacking the top item if it is not a integer
    while (this._stack.length > 0 && !this._stack[this._stack.length - 1].isInteger()) {
        const list = this._stack.pop().getList();
        // Add into stack in reverse order to match the processing order
        for (let i = list.length - 1; i >= 0; i--) {
            this._stack.push(list[i])
        }
    }
};

Binary Tree Iterator for Inorder Traversal

Given a Binary Tree and an input array. The task is to create an Iterator that utilizes next() and hasNext() functions to perform Inorder traversal on the binary tree.

Approach

Before we implement the iterator, let’s recap the iterative version of inorder traversal.

1. Two while loops are needed.
2. First while loop takes care of finding the ancestor.
3. Second while loop traverse the ancestor to leaf node to implement in-order rule.
4. Once second loop is exhausted, it means we reached to the left most node of the subtree.
5. Remove the item from stack to process it.
6. To discover the next ancestor, explore the right subtree.

Following is in-order traversal for reference.

var inorderTraversal = function(root) {
    const ans = [];
    const stack = [];
    let node = root;
    while(stack.length > 0 || node) {
        // Keep traversing left
        while(node) {
            stack.push(node);
            node = node.left; 
        }
        
        // pop node from stack for processing
        node = stack.pop();
        
        // process node
        ans.push(node.val);
        
        // advance node with right child for upper while loop
        node = node.right;
    }
    return ans;
};

Similarity, to implement hasNext() and next() for iterator, we will have to do following

1. Initialize stack with the all the left nodes of the root as ancestor.
2. hasNext() will simply return true if stack is not empty otherwise false
3. As it sounds, since when stack is empty, it doesn’t mean we have exhausted tree traversal. Therefore we will have to keep checking right subtree in the next() to make sure stack is kept populated for next set of nodes.
4. next() will first remove top item from stack for processing.
5. If it does have right subtree, then insert all the left elements of right subtree into stack
6. Return the item removed from top.

Following is code for reference.

/**
 * @param {TreeNode} root
 */
var BTIterator = function (root) {
    this.root = root;
    this.stack = [];
    this.current = root;
    while (this.current) {
        this.stack.push(this.current);
        this.current = this.current.left;
    }
};

/**
 * @return {number}
 */
BTIterator.prototype.next = function () {
    const top = this.stack.pop();
    if (top.right) {
        let node = top.right;
        while (node) {
            this.stack.push(node);
            node = node.left;
        }
    }
    return top.val;
};

/**
 * @return {boolean}
 */
BTIterator.prototype.hasNext = function () {
    return this.stack.length > 0;
};

Prev & hasPrev() for Inorder Traversal

Can we extend above iteterator with hasPrev() and prev() ?

1. Yes, we can.
2. We will introduce seen and pointer to track the previously traversed items.
3. If pointer is out of precomputed seen then only next() will run calculation to perform.
4. Otherwise use seen[pointer] for next()

Following is updated one.

/**
 * @param {TreeNode} root
 */
var BSTIterator = function (root) {
    this.root = root;
    this.stack = [];
    this.current = root;
    this.pointer = -1;
    this.seen = [];
    while (this.current) {
        this.stack.push(this.current);
        this.current = this.current.left;
    }
};

/**
 * @return {boolean}
 */
BSTIterator.prototype.hasNext = function () {
    return this.stack.length > 0 || this.pointer < this.seen.length - 1;
};

/**
 * @return {number}
 */
BSTIterator.prototype.next = function () {
    this.pointer++;
    // If pointer is out of precomputed rage
    if (this.pointer === this.seen.length) {
        const top = this.stack.pop();
        if (top.right) {
            let node = top.right;
            while (node) {
                this.stack.push(node);
                node = node.left;
            }
        }
        this.seen.push(top);
    }
    return this.seen[this.pointer].val;
};

/**
 * @return {boolean}
 */
BSTIterator.prototype.hasPrev = function () {
    return this.pointer > 0;
};

/**
 * @return {number}
 */
BSTIterator.prototype.prev = function () {
    --this.pointer;
    return this.seen[this.pointer].val;
};

/** 
 * Your BSTIterator object will be instantiated and called as such:
 * var obj = new BSTIterator(root)
 * var param_1 = obj.hasNext()
 * var param_2 = obj.next()
 * var param_3 = obj.hasPrev()
 * var param_4 = obj.prev()
 */

173. Binary Search Tree Iterator

https://leetcode.com/problems/binary-search-tree-iterator/description/

Implement the BSTIterator class that represents an iterator over the in-order traversal of a binary search tree (BST):

• BSTIterator(TreeNode root) Initializes an object of the BSTIterator class. The root of the BST is given as part of the constructor. The pointer should be initialized to a non-existent number smaller than any element in the BST.
• boolean hasNext() Returns true if there exists a number in the traversal to the right of the pointer, otherwise returns false.
• int next() Moves the pointer to the right, then returns the number at the pointer.

Notice that by initializing the pointer to a non-existent smallest number, the first call to next() will return the smallest element in the BST.

You may assume that next() calls will always be valid. That is, there will be at least a next number in the in-order traversal when next() is called.

Example 1:

Input
["BSTIterator", "next", "next", "hasNext", "next", "hasNext", "next", "hasNext", "next", "hasNext"]
[[[7, 3, 15, null, null, 9, 20]], [], [], [], [], [], [], [], [], []]
Output
[null, 3, 7, true, 9, true, 15, true, 20, false]

Approach#1: Simply run in-order traversal for hasNext() and next()

We can treat Binary search tree as a general binary tree and implement the in-order traversal approach as discussed in above problem to implement the iterator.

Not writing code here as it would be exactly same as above.

Approach #2: Leverage the binary search properties to optimize it

1. Instead of storing intermediate nodes in stack , we can leverage the BST properties.
2. Goal here is same i.e. identify the ancestor and then keep scanning left nodes to find out the minimum value as the next.
3. We will initialize current as minimum value of root as anecestor.
4. hasNext() will return true if current is not null, otherwise false
5. next() will return the value of current . But before it returns, it has to find out ancestor of current as next current node as below.
6. If current has right subtree, the simply scan all the left nodes of right subtree to find out the minimum value which will act as next subtree.

7. Otherwise, the last node which took the left turn will be the next ancestor.

Following is code for reference.

const getMin = (root) => {
    // get left most node
    let node = root;
    while (node.left) {
        node = node.left;
    }
    return node;
}
const getSuccessor = (root, current) => {
    // if node has right child then get min in the right subtree
    if (current.right) {
        return getMin(current.right);
    }
    // get the ancestor who took first left turn
    let node = root;
    let ancestor = null;
    // keep searching for node
    while (node !== current) {
        if (current.val < node.val) {
            // track the node taking left turn
            ancestor = node;
            node = node.left;
        } else {
            node = node.right;
        }
    }
    return ancestor;
}
/**
 * @param {TreeNode} root
 */
var BSTIterator = function (root) {
    this.root = root;
    this.current = getMin(root);
};

/**
 * @return {number}
 */
BSTIterator.prototype.next = function () {
    const ans = this.current;
    this.current = getSuccessor(this.root, this.current);
    return ans.val;
};

/**
 * @return {boolean}
 */
BSTIterator.prototype.hasNext = function () {
    return !!this.current;
};

1586. Binary Search Tree Iterator II

https://leetcode.com/problems/binary-search-tree-iterator-ii/description

Implement the BSTIterator class that represents an iterator over the in-order traversal of a binary search tree (BST):

• BSTIterator(TreeNode root) Initializes an object of the BSTIterator class. The root of the BST is given as part of the constructor. The pointer should be initialized to a non-existent number smaller than any element in the BST.
• boolean hasNext() Returns true if there exists a number in the traversal to the right of the pointer, otherwise returns false.
• int next() Moves the pointer to the right, then returns the number at the pointer.
• boolean hasPrev() Returns true if there exists a number in the traversal to the left of the pointer, otherwise returns false.
• int prev() Moves the pointer to the left, then returns the number at the pointer.

Notice that by initializing the pointer to a non-existent smallest number, the first call to next() will return the smallest element in the BST.

You may assume that next() and prev() calls will always be valid. That is, there will be at least a next/previous number in the in-order traversal when next()/prev() is called.

Example 1:

Input
["BSTIterator", "next", "next", "prev", "next", "hasNext", "next", "next", "next", "hasNext", "hasPrev", "prev", "prev"]
[[[7, 3, 15, null, null, 9, 20]], [null], [null], [null], [null], [null], [null], [null], [null], [null], [null], [null], [null]]
Output
[null, 3, 7, 3, 7, true, 9, 15, 20, false, true, 15, 9]

Approach #1: Use in-order traversal

We can simply use the general binary tree in-order traversal approach for prev & next as well.

Approach #2: Use getMin(), getMax(), successor and predecessor

TBD

1286. Iterator for Combination

https://leetcode.com/problems/iterator-for-combination/description/

TBD

900. RLE Iterator

https://leetcode.com/problems/rle-iterator/description/

We can use run-length encoding (i.e., RLE) to encode a sequence of integers. In a run-length encoded array of even length encoding (0-indexed), for all even i, encoding[i] tells us the number of times that the non-negative integer value encoding[i + 1] is repeated in the sequence.

• For example, the sequence arr = [8,8,8,5,5] can be encoded to be encoding = [3,8,2,5]. encoding = [3,8,0,9,2,5] and encoding = [2,8,1,8,2,5] are also valid RLE of arr.

Given a run-length encoded array, design an iterator that iterates through it.

Implement the RLEIterator class:

• RLEIterator(int[] encoded) Initializes the object with the encoded array encoded.
• int next(int n) Exhausts the next n elements and returns the last element exhausted in this way. If there is no element left to exhaust, return -1 instead.

Example 1:

Input
["RLEIterator", "next", "next", "next", "next"]
[[[3, 8, 0, 9, 2, 5]], [2], [1], [1], [2]]
Output
[null, 8, 8, 5, -1]

Approach

1. Track the curr index.
2. Keep trying until n>0
3. If index is greater than the size then return -1
4. Consume the current encoding size
5. If it is greater than zero then it means current position can’t serve the asked n , so we need to move to reduce and move to next.
6. Otherwise, read the number and updating consumed pattern.

Following is code for reference.

/**
 * @param {number[]} encoding
 */
var RLEIterator = function (encoding) {
    this.encoding = encoding;
    this.curr = 0;
};

/** 
 * @param {number} n
 * @return {number}
 */
RLEIterator.prototype.next = function (n) {
    let num = 0;
    while (n > 0) {
        if (this.curr >= this.encoding.length) {
            return -1;
        }
        n = n - this.encoding[this.curr];
        if (n <= 0) {
            // Read number
            num = this.encoding[this.curr + 1];
            // Reduce current usage
            this.encoding[this.curr] = -n;
        } else {
            this.curr += 2;
        }
    }
    return num;
};

/** 
 * Your RLEIterator object will be instantiated and called as such:
 * var obj = new RLEIterator(encoding)
 * var param_1 = obj.next(n)
 */

Happy coding.