You are given a binary array pattern and an object stream of class InfiniteStream representing a 0-indexed infinite stream of bits.
The class InfiniteStream contains the following function:
int next(): Reads a single bit (which is either 0 or 1) from the stream and returns it.Return the first starting index where the pattern matches the bits read from the stream. For example, if the pattern is [1, 0], the first match is the highlighted part in the stream [0, 1, 0, 1, ...].
Example 1:
Input: stream = [1,1,1,0,1,1,1,...], pattern = [0,1] Output: 3 Explanation: The first occurrence of the pattern [0,1] is highlighted in the stream [1,1,1,0,1,...], which starts at index 3.
Example 2:
Input: stream = [0,0,0,0,...], pattern = [0] Output: 0 Explanation: The first occurrence of the pattern [0] is highlighted in the stream [0,...], which starts at index 0.
Example 3:
Input: stream = [1,0,1,1,0,1,1,0,1,...], pattern = [1,1,0,1] Output: 2 Explanation: The first occurrence of the pattern [1,1,0,1] is highlighted in the stream [1,0,1,1,0,1,...], which starts at index 2.
Constraints:
1 <= pattern.length <= 104pattern consists only of 0 and 1.stream consists only of 0 and 1.105 bits of the stream.Problem Overview: You receive numbers from an infinite stream through an API like next(). Given a finite pattern array, return the first index where this pattern appears in the stream. Since the stream is unbounded, you cannot store everything; the algorithm must process elements incrementally and detect the match as soon as the pattern appears.
Approach 1: Brute Force Sliding Window (O(n * m) time, O(m) space)
The direct approach keeps a window of the last m elements, where m is the pattern length. Each time you read a new value from the stream, append it to the window and compare the entire window with the pattern element by element. If they match, return the starting index. Otherwise shift the window by one and repeat. This uses a simple sliding window buffer but performs a full comparison for every step, which makes it inefficient when the stream runs for a long time before the pattern appears.
Approach 2: Rolling Hash (Rabin–Karp) (O(n) time, O(m) space)
A faster solution treats the pattern matching task as a streaming version of classic string matching. Precompute a hash for the pattern. While reading elements from the stream, maintain a rolling hash for the current window of size m. Each new element updates the hash by removing the contribution of the outgoing element and adding the new one. If the rolling hash equals the pattern hash, verify the window to avoid collisions. This avoids repeated full comparisons and turns the search into near linear time.
The rolling hash relies on a polynomial hash or modular base exponentiation from the hash function family. Because the window moves one element at a time, updating the hash costs O(1). The algorithm stores only the current window and a few hash parameters, which keeps memory bounded even though the stream is infinite.
Recommended for interviews: The rolling hash (Rabin–Karp) solution is the expected approach. The brute force sliding window shows you understand the streaming constraint, but the optimized hashing approach demonstrates knowledge of string matching algorithms and efficient incremental computation. Interviewers look for the ability to process unbounded input while maintaining O(1) update work per element.
Solutions for this problem are being prepared.
Try solving it yourself| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Sliding Window | O(n * m) | O(m) | Simple implementation or when pattern length is very small |
| Rolling Hash (Rabin–Karp) | O(n) | O(m) | General case for large streams where efficient incremental matching is required |
3037. Find Pattern in Infinite Stream II (Leetcode Hard) • Programming Live with Larry • 206 views views
Watch 1 more video solutions →Practice Find Pattern in Infinite Stream II with our built-in code editor and test cases.
Practice on FleetCode