Scale Engineer

Iterator for Combination

Med
#1198Time: Constructor: `O(K)` to initialize the `indices` array. `next()`: `O(K)`. In the worst case, we scan the entire `indices` array (`O(K)`) to find the pivot, and building the result string also takes `O(K)`. `hasNext()`: `O(1)`.Space: O(K), where K is the `combinationLength`, to store the `indices` array.
Patterns
BacktrackingDesignIterator
Data structures
String

Prompt

Design the CombinationIterator class:

  • CombinationIterator(string characters, int combinationLength) Initializes the object with a string characters of sorted distinct lowercase English letters and a number combinationLength as arguments.
  • next() Returns the next combination of length combinationLength in lexicographical order.
  • hasNext() Returns true if and only if there exists a next combination.

 

Example 1:

Input
["CombinationIterator", "next", "hasNext", "next", "hasNext", "next", "hasNext"]
[["abc", 2], [], [], [], [], [], []]
Output
[null, "ab", true, "ac", true, "bc", false]

Explanation
CombinationIterator itr = new CombinationIterator("abc", 2);
itr.next();    // return "ab"
itr.hasNext(); // return True
itr.next();    // return "ac"
itr.hasNext(); // return True
itr.next();    // return "bc"
itr.hasNext(); // return False

 

Constraints:

  • 1 <= combinationLength <= characters.length <= 15
  • All the characters of characters are unique.
  • At most 104 calls will be made to next and hasNext.
  • It is guaranteed that all calls of the function next are valid.

Approaches

2 approaches with complexity analysis and trade-offs.

This highly efficient approach avoids pre-computing all combinations. Instead, it calculates the next combination only when the next() method is called. It maintains the state of the current combination using an array of indices that point to characters in the input string, a technique often used for generating combinations iteratively.

Algorithm

  • CombinationIterator(characters, combinationLength):
    1. Store characters, its length n, and combinationLength k.
    2. Initialize an integer array indices of size k.
    3. Populate indices to represent the first combination: indices[i] = i for i from 0 to k-1.
    4. Set a boolean flag hasNextFlag = true.
  • next():
    1. Build the result string for the current combination by looking up characters using the values in the indices array.
    2. Prepare the indices for the next call. Find the rightmost index i that can be incremented. An index indices[i] can be incremented if it's not at its maximum possible value, which is i + n - k.
    3. Scan from i = k-1 down to 0 to find the first index that is not at its maximum value.
    4. If no such index is found, it means the current combination is the last one. Set hasNextFlag = false.
    5. If an index i is found: a. Increment indices[i]. b. For all subsequent indices j > i, set indices[j] = indices[j-1] + 1 to form the next lexicographically smallest combination.
    6. Return the string built in step 1.
  • hasNext():
    1. Return the hasNextFlag.

Walkthrough

The state of the iterator is represented by an array of integers, indices, of size combinationLength. Each integer in this array is an index into the original characters string. The constructor initializes this array to [0, 1, ..., k-1], representing the first lexicographical combination.

The next() method performs two main tasks: it first constructs the string for the current indices and then updates the indices array to point to the next combination. To find the next combination, we scan the indices array from right to left, looking for the first index we can increment. Once we find such an index, we increment it and then reset all subsequent indices to be consecutive values following it. This guarantees that we move to the very next combination in lexicographical order. If we scan the whole array and find that all indices are at their maximum possible values, we know there are no more combinations left.

class CombinationIterator {    private String characters;    private int n;    private int k;    private int[] indices;    private boolean hasNext;     public CombinationIterator(String characters, int combinationLength) {        this.characters = characters;        this.n = characters.length();        this.k = combinationLength;        this.indices = new int[k];        // Initialize to the first combination: [0, 1, ..., k-1]        for (int i = 0; i < k; i++) {            this.indices[i] = i;        }        this.hasNext = true;    }     public String next() {        // Build the current combination string        StringBuilder sb = new StringBuilder();        for (int index : indices) {            sb.append(characters.charAt(index));        }                // Find the next combination's indices for the subsequent call        // Start from the rightmost index and find the first one that can be incremented.        int i = k - 1;        while (i >= 0 && indices[i] == i + n - k) {            i--;        }         if (i < 0) {            // This was the last combination            this.hasNext = false;        } else {            // Increment this index            indices[i]++;            // Reset all subsequent indices            for (int j = i + 1; j < k; j++) {                indices[j] = indices[j - 1] + 1;            }        }                return sb.toString();    }     public boolean hasNext() {        return this.hasNext;    }}

Complexity

Time

Constructor: `O(K)` to initialize the `indices` array. `next()`: `O(K)`. In the worst case, we scan the entire `indices` array (`O(K)`) to find the pivot, and building the result string also takes `O(K)`. `hasNext()`: `O(1)`.

Space

O(K), where K is the `combinationLength`, to store the `indices` array.

Trade-offs

Pros

  • Extremely memory efficient, using only space proportional to the combination length.

  • Fast initialization (O(K)), as no heavy computation is done upfront.

  • Work is distributed across next() calls (lazy evaluation), which is ideal for typical iterator usage patterns.

Cons

  • The logic inside the next() method is more complex than in the pre-computation approach.

  • Each next() call has a slightly higher cost (O(K)) compared to the O(1) of the pre-computation approach.

Solutions

class CombinationIterator { private int n ; private int combinationLength ; private String characters ; private StringBuilder t = new StringBuilder (); private List < String > cs = new ArrayList <>(); private int idx = 0 ; public CombinationIterator ( String characters , int combinationLength ) { n = characters . length (); this . combinationLength = combinationLength ; this . characters = characters ; dfs ( 0 ); } public String next () { return cs . get ( idx ++); } public boolean hasNext () { return idx < cs . size (); } private void dfs ( int i ) { if ( t . length () == combinationLength ) { cs . add ( t . toString ()); return ; } if ( i == n ) { return ; } t . append ( characters . charAt ( i )); dfs ( i + 1 ); t . deleteCharAt ( t . length () - 1 ); dfs ( i + 1 ); } } /** * Your CombinationIterator object will be instantiated and called as such: * CombinationIterator obj = new CombinationIterator(characters, combinationLength); * String param_1 = obj.next(); * boolean param_2 = obj.hasNext(); */

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem