Is Iterator for Combination easy or hard?

Iterator for Combination is rated Medium because it combines combination generation with object-oriented iterator design. The logic for computing the next lexicographic combination requires careful index manipulation.

Iterator for Combination Python/Java solution

In Python, combinations are often generated using backtracking with a list storing all results or with an index pointer for on-demand generation. Java implementations typically store indices in an int array and update them lexicographically to produce the next combination string.

How to solve Iterator for Combination in O(n)?

The full problem cannot be solved in O(n) overall because the iterator must eventually produce C(n,k) combinations. However, each call to next() can run in about O(k) time by updating the combination indices and rebuilding the string from the original characters.

What is the best approach for Iterator for Combination?

The most practical approach is generating combinations on the fly using a lexicographical index array. It stores only the current combination indices and updates them to produce the next combination. This keeps space complexity at O(k) while still generating all C(n,k) combinations in order.

Is Iterator for Combination asked at Google/Amazon/Meta?

Iterator and design-style problems like this frequently appear in interviews at large tech companies including Google, Amazon, and Meta. They test understanding of iterator patterns, combination generation, and maintaining internal state between calls.

What data structure is used in Iterator for Combination?

Most implementations use an array or list of indices to represent the current combination. Backtracking or iterative index updates generate the next combination while preserving lexicographic order.

What is the time complexity of Iterator for Combination?

Generating all combinations requires O(C(n,k) * k) time because each combination of length k must be constructed. In the precomputation approach this cost occurs during initialization, while in the iterator approach it is distributed across calls to next().

Description Hints 2 Solution Video 23:43

1286. Iterator for Combination

Medium72.7% acceptance1 company

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 10⁴ calls will be made to next and hasNext.
It is guaranteed that all calls of the function next are valid.

Asked at 1 company

Google

Topics

Hints open one at a time

Hint 1

Generate all combinations as a preprocessing.

Hint 2

Use bit masking to generate all the combinations.

23:43

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class CombinationIterator:
2 
3    def __init__(self, characters: str, combinationLength: int):
4        
5 
6    def next(self) -> str:
7        
8 
9    def hasNext(self) -> bool:
10        
11 
12 
13# Your CombinationIterator object will be instantiated and called as such:
14# obj = CombinationIterator(characters, combinationLength)
15# param_1 = obj.next()
16# param_2 = obj.hasNext()

Starter codePython 3Spaces: 4

Examples

Case 1

Input

["CombinationIterator","next","hasNext","next","hasNext","next","hasNext"]
[["abc",2],[],[],[],[],[],[]]

Your code is saved on this device.Solution