LeetCode 3023 - Find Pattern in Infinite Stream I
The problem asks us to detect the first occurrence of a given binary pattern within an infinite stream of bits. We are given an object stream that allows us to read one bit at a time using the next() function.
Difficulty: 🟡 Medium
Topics: Array, Sliding Window, Rolling Hash, String Matching, Interactive, Hash Function
Solution
Problem Understanding
The problem asks us to detect the first occurrence of a given binary pattern within an infinite stream of bits. We are given an object stream that allows us to read one bit at a time using the next() function. Our task is to return the 0-based index in the stream where the pattern begins.
In simpler terms, imagine the stream as an endless sequence of 0s and 1s, and we have a short sequence (pattern) that we want to locate. We cannot look ahead in the stream arbitrarily; we can only read one bit at a time. The function must identify the first index where the stream matches the entire pattern consecutively.
The constraints tell us that the pattern length is modest (up to 100) and the first occurrence is guaranteed to appear within the first 105 bits. This indicates that although the stream is conceptually infinite, we only need to read a bounded number of bits.
Important edge cases include patterns of length 1, streams starting with the pattern, streams that almost match but differ at the last bit, and repetitive streams that could mislead naive approaches. Since the first occurrence is guaranteed within 105 bits, we don’t need to handle the case of a pattern never occurring.
Approaches
Brute Force
The brute-force approach reads one bit at a time and keeps a sliding window of the last pattern.length bits. After each new bit, we compare the window to the pattern element by element. If all elements match, we return the current starting index. This works correctly because it explicitly checks each possible starting position for the pattern.
However, the approach is inefficient because for each new bit read, we perform up to pattern.length comparisons. In the worst case, for a pattern of length m and up to 105 bits read, this results in O(m * n) operations, which can be acceptable here due to constraints but is not optimal. For larger streams or longer patterns, this would be too slow.
Optimal Approach - Rolling Hash
The key insight is that we can use a rolling hash to compare sequences efficiently. By treating the pattern as a binary number and maintaining a hash of the last pattern.length bits, we can update the hash in O(1) time each step. If the rolling hash matches the pattern hash, we have a candidate match, and we only need to do a single verification check to avoid hash collisions. This reduces the per-bit comparison from O(m) to O(1) on average.
For a binary sequence, the rolling hash can be computed as follows: multiply the current hash by 2, add the new bit, and remove the bit that falls out of the window. This works like a sliding window representation of the binary sequence as an integer.
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(n * m) | O(m) | Compares the sliding window to the pattern at each step |
| Optimal | O(n) | O(1) | Uses a rolling hash for efficient pattern detection |
Algorithm Walkthrough
- Compute the binary integer value of the pattern. This is the target hash we will look for.
- Initialize a rolling hash for the stream as 0.
- Read bits from the stream one by one, updating the rolling hash:
- Multiply the current hash by 2 (shift left)
- Add the new bit
- If the window size exceeds
pattern.length, remove the oldest bit from the hash
- After updating the hash, if the rolling hash equals the pattern hash and we have read at least
pattern.lengthbits, verify the current window matches the pattern exactly. - If verified, return the starting index, which is the current index minus
pattern.length+ 1. - Continue until the first match is found (guaranteed to exist within the first 105 bits).
Why it works: The rolling hash uniquely encodes the last pattern.length bits as an integer, so matching hashes indicate a potential match. Verification ensures correctness despite possible collisions, and because the first occurrence is guaranteed, we will always terminate with the correct starting index.
Python Solution
from typing import List, Optional
# Definition for an infinite stream.
# class InfiniteStream:
# def next(self) -> int:
# pass
class Solution:
def findPattern(self, stream: Optional['InfiniteStream'], pattern: List[int]) -> int:
m = len(pattern)
target_hash = 0
for bit in pattern:
target_hash = (target_hash << 1) | bit
window_hash = 0
mask = (1 << m) - 1 # To keep only the last m bits
index = 0
while True:
bit = stream.next()
window_hash = ((window_hash << 1) | bit) & mask
if index >= m - 1:
if window_hash == target_hash:
# Verify to prevent hash collision
# We need to re-read last m bits; we assume we can keep a buffer
buffer = [0] * m
# Shift window_hash into buffer
temp = window_hash
for i in range(m-1, -1, -1):
buffer[i] = temp & 1
temp >>= 1
if buffer == pattern:
return index - m + 1
index += 1
Implementation Walkthrough: The code first computes the integer representation of the pattern. We maintain a rolling hash for the last m bits. The mask ensures we only keep m bits at all times. When the hash matches, we reconstruct the current window into a list for verification. The index counter tracks the position in the infinite stream.
Go Solution
/**
* Definition for an infinite stream.
* type InfiniteStream interface {
* Next() int
* }
*/
func findPattern(stream InfiniteStream, pattern []int) int {
m := len(pattern)
targetHash := 0
for _, bit := range pattern {
targetHash = (targetHash << 1) | bit
}
windowHash := 0
mask := (1 << m) - 1
index := 0
buffer := make([]int, 0, m)
for {
bit := stream.Next()
windowHash = ((windowHash << 1) | bit) & mask
buffer = append(buffer, bit)
if len(buffer) > m {
buffer = buffer[1:]
}
if index >= m - 1 {
if windowHash == targetHash {
match := true
for i := 0; i < m; i++ {
if buffer[i] != pattern[i] {
match = false
break
}
}
if match {
return index - m + 1
}
}
}
index++
}
}
Go Notes: Go does not allow slicing integers easily, so we maintain a slice buffer to verify a candidate match. Everything else mirrors the Python implementation: compute rolling hash, use mask, verify when necessary, and maintain the stream index.
Worked Examples
Example 1
Stream: [1,1,1,0,1,...]
Pattern: [0,1]
| Step | Stream Bit | Window | Window Hash | Index | Matches Pattern? |
|---|---|---|---|---|---|
| 0 | 1 | [1] | 1 | 0 | No |
| 1 | 1 | [1,1] | 3 | 1 | No |
| 2 | 1 | [1,1] | 3 | 2 | No |
| 3 | 0 | [1,0] | 2 | 3 | No |
| 4 | 1 | [0,1] | 1 | 4 | Yes → return 3 |
Example 2
Stream: [0,0,0,0,...]
Pattern: [0]
| Step | Stream Bit | Window | Window Hash | Index | Matches Pattern? |
|---|---|---|---|---|---|
| 0 | 0 | [0] | 0 | 0 | Yes → return 0 |
Example 3
Stream: [1,0,1,1,0,1,1,0,1,...]
Pattern: [1,1,0,1]
| Step | Window | Window Hash | Index | Matches Pattern? |
|---|---|---|---|---|
| 0-1 | ... | ... | ... | No |
| 2 | [1,1,0,1] | 13 | 5 | Yes → return 2 |
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n) | Each bit is read once and rolling hash updated in O(1). Verification also takes O(m), but happens only when hash matches, which is rare. |
| Space | O(m) | We maintain a buffer of size m for verification and store pattern hash. |
The time complexity is efficient given that n <= 105, and space is minimal and independent of the infinite stream.
Test Cases
# Basic examples
assert Solution().findPattern(stream=InfiniteStream([1,1,1,0,1]), pattern=[0,1]) == 3 # Example 1