Find Pattern in Infinite Stream II

Problem

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 thefirst 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, ...].

Examples

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 <= 10^4
• pattern consists only of 0 and 1.
• stream consists only of 0 and 1.
• The input is generated such that the pattern's start index exists in the first 105 bits of the stream.

Solution

Method 1 – KMP (Knuth-Morris-Pratt) Pattern Matching

Intuition

KMP preprocesses the pattern to build a "failure function" (lps array) that allows us to skip unnecessary comparisons. As we read the stream, we track how much of the pattern matches so far, and efficiently reset when a mismatch occurs.

Approach

1. Precompute the lps (longest prefix-suffix) array for the pattern.
2. Initialize a pointer j for the pattern.
3. For each bit from the stream:
   • While j > 0 and the bit doesn't match pattern[j], set j = lps[j-1].
   • If the bit matches, increment j.
   • If j == len(pattern), return the current index minus pattern length + 1 (match found).
4. Continue until a match is found.

Code

C++

class Solution {
public:
    int findPattern(InfiniteStream& stream, vector<int>& pattern) {
        int n = pattern.size();
        vector<int> lps(n, 0);
        for (int i = 1, len = 0; i < n; ) {
            if (pattern[i] == pattern[len]) lps[i++] = ++len;
            else if (len) len = lps[len-1];
            else lps[i++] = 0;
        }
        int j = 0, idx = 0;
        while (true) {
            int bit = stream.next();
            while (j > 0 && bit != pattern[j]) j = lps[j-1];
            if (bit == pattern[j]) j++;
            if (j == n) return idx - n + 1;
            idx++;
        }
    }
};

Go

func findPattern(stream InfiniteStream, pattern []int) int {
    n := len(pattern)
    lps := make([]int, n)
    for i, l := 1, 0; i < n; {
        if pattern[i] == pattern[l] {
            l++
            lps[i] = l
            i++
        } else if l > 0 {
            l = lps[l-1]
        } else {
            lps[i] = 0
            i++
        }
    }
    j, idx := 0, 0
    for {
        bit := stream.Next()
        for j > 0 && bit != pattern[j] {
            j = lps[j-1]
        }
        if bit == pattern[j] {
            j++
        }
        if j == n {
            return idx - n + 1
        }
        idx++
    }
}

Java

class Solution {
    public int findPattern(InfiniteStream stream, int[] pattern) {
        int n = pattern.length;
        int[] lps = new int[n];
        for (int i = 1, len = 0; i < n; ) {
            if (pattern[i] == pattern[len]) lps[i++] = ++len;
            else if (len > 0) len = lps[len-1];
            else lps[i++] = 0;
        }
        int j = 0, idx = 0;
        while (true) {
            int bit = stream.next();
            while (j > 0 && bit != pattern[j]) j = lps[j-1];
            if (bit == pattern[j]) j++;
            if (j == n) return idx - n + 1;
            idx++;
        }
    }
}

Kotlin

class Solution {
    fun findPattern(stream: InfiniteStream, pattern: IntArray): Int {
        val n = pattern.size
        val lps = IntArray(n)
        var len = 0
        var i = 1
        while (i < n) {
            if (pattern[i] == pattern[len]) lps[i++] = ++len
            else if (len > 0) len = lps[len-1]
            else lps[i++] = 0
        }
        var j = 0
        var idx = 0
        while (true) {
            val bit = stream.next()
            while (j > 0 && bit != pattern[j]) j = lps[j-1]
            if (bit == pattern[j]) j++
            if (j == n) return idx - n + 1
            idx++
        }
    }
}

Python

class Solution:
    def findPattern(self, stream: 'InfiniteStream', pattern: list[int]) -> int:
        n = len(pattern)
        lps = [0] * n
        l = 0
        for i in range(1, n):
            while l > 0 and pattern[i] != pattern[l]:
                l = lps[l-1]
            if pattern[i] == pattern[l]:
                l += 1
                lps[i] = l
        j = 0
        idx = 0
        while True:
            bit = stream.next()
            while j > 0 and bit != pattern[j]:
                j = lps[j-1]
            if bit == pattern[j]:
                j += 1
            if j == n:
                return idx - n + 1
            idx += 1

Rust

impl Solution {
    pub fn find_pattern(stream: &mut InfiniteStream, pattern: Vec<i32>) -> i32 {
        let n = pattern.len();
        let mut lps = vec![0; n];
        let mut len = 0;
        for i in 1..n {
            while len > 0 && pattern[i] != pattern[len] {
                len = lps[len - 1];
            }
            if pattern[i] == pattern[len] {
                len += 1;
                lps[i] = len;
            }
        }
        let mut j = 0;
        let mut idx = 0;
        loop {
            let bit = stream.next();
            while j > 0 && bit != pattern[j] {
                j = lps[j - 1];
            }
            if bit == pattern[j] {
                j += 1;
            }
            if j == n {
                return idx as i32 - n as i32 + 1;
            }
            idx += 1;
        }
    }
}

TypeScript

class Solution {
    findPattern(stream: InfiniteStream, pattern: number[]): number {
        const n = pattern.length;
        const lps = new Array(n).fill(0);
        for (let i = 1, len = 0; i < n;) {
            if (pattern[i] === pattern[len]) lps[i++] = ++len;
            else if (len > 0) len = lps[len-1];
            else lps[i++] = 0;
        }
        let j = 0, idx = 0;
        while (true) {
            const bit = stream.next();
            while (j > 0 && bit !== pattern[j]) j = lps[j-1];
            if (bit === pattern[j]) j++;
            if (j === n) return idx - n + 1;
            idx++;
        }
    }
}

Complexity

• ⏰ Time complexity: O(N + M), where N is the index of the first match (at most 1e5), and M is the pattern length (≤ 10^4), due to KMP preprocessing and matching.
• 🧺 Space complexity: O(M), for the lps array and pattern window.