Watch the video solution for Find Pattern in Infinite Stream I, a medium level problem involving Array, Sliding Window, Rolling Hash. This walkthrough by Programming Live with Larry has 355 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 100pattern consists only of 0 and 1.stream consists only of 0 and 1.105 bits of the stream.Problem Overview: You receive bits from an infinite stream one at a time and must detect when a given binary pattern appears. The stream never ends, so you cannot store the entire input. The goal is to continuously read values and determine whether the last m bits match the target pattern.
Approach 1: Brute Force Stream Comparison (O(n * m) time, O(m) space)
The simplest idea stores the last m values from the stream and compares them to the pattern after each new bit arrives. Maintain a buffer of size m. Every time you call next(), shift the window and perform an element‑by‑element comparison against the pattern array. This works but each check costs O(m), making the overall complexity O(n * m) for n processed bits. The approach demonstrates the core sliding window idea but is inefficient for large patterns.
Approach 2: Rolling Hash / String Matching (O(n) time, O(1) space)
Instead of comparing the whole window each time, treat the pattern as a binary number and maintain a rolling hash for the last m bits of the stream. Each new bit shifts the previous hash left and inserts the new value, while masking out bits that fall outside the window. This technique is similar to string matching algorithms such as Rabin–Karp. Because the update takes constant time and comparison is a single integer equality check, the stream can be processed in O(n) time with O(1) extra memory.
Approach 3: Bit Manipulation + Sliding Window (O(n) time, O(1) space)
The optimal implementation uses bit manipulation to maintain a compact representation of the current window. Convert the pattern into an integer mask. While reading bits from the stream, maintain a rolling integer window: window = ((window << 1) | bit) & maskLimit. The mask trims the window to exactly m bits. When window == patternMask, the pattern has appeared in the stream. This approach combines array processing with a sliding window and bitwise operations, giving constant memory and extremely fast updates.
Recommended for interviews: Interviewers expect the bit manipulation sliding window solution. Starting with the brute force buffer comparison shows you understand the streaming constraint, but the optimized rolling window demonstrates strong knowledge of hashing and windowed pattern matching in continuous data streams.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Window Comparison | O(n * m) | O(m) | Good for understanding the streaming constraint and initial brute force logic. |
| Rolling Hash (Rabin–Karp style) | O(n) | O(1) | Efficient pattern detection in streaming or substring search problems. |
| Bit Manipulation + Sliding Window | O(n) | O(1) | Optimal for binary streams where the pattern length is small enough to fit in an integer mask. |