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:

1
2
3

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:

1
2
3

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:

1
2
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 <= 100
  • 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 – Sliding Window (Brute Force)

Intuition

We read bits from the stream one by one, maintaining a window of the last len(pattern) bits. At each step, we check if the window matches the pattern. The first time it matches, we return the starting index.

Approach

  1. Initialize an empty list or queue to store the last len(pattern) bits.
  2. For each bit read from the stream:
    • Add the bit to the window.
    • If the window size exceeds the pattern length, remove the oldest bit.
    • If the window matches the pattern, return the current index minus pattern length + 1.
  3. Continue until a match is found.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
public:
    int findPattern(InfiniteStream& stream, vector<int>& pattern) {
        int n = pattern.size();
        deque<int> window;
        int idx = 0;
        while (true) {
            int bit = stream.next();
            window.push_back(bit);
            if (window.size() > n) window.pop_front();
            if (window.size() == n && vector<int>(window.begin(), window.end()) == pattern)
                return idx - n + 1;
            idx++;
        }
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

func findPattern(stream InfiniteStream, pattern []int) int {
    n := len(pattern)
    window := make([]int, 0, n)
    idx := 0
    for {
        bit := stream.Next()
        window = append(window, bit)
        if len(window) > n {
            window = window[1:]
        }
        if len(window) == n {
            match := true
            for i := 0; i < n; i++ {
                if window[i] != pattern[i] {
                    match = false
                    break
                }
            }
            if match {
                return idx - n + 1
            }
        }
        idx++
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    public int findPattern(InfiniteStream stream, int[] pattern) {
        int n = pattern.length, idx = 0;
        Deque<Integer> window = new ArrayDeque<>();
        while (true) {
            int bit = stream.next();
            window.addLast(bit);
            if (window.size() > n) window.pollFirst();
            if (window.size() == n) {
                int i = 0;
                for (int b : window) {
                    if (b != pattern[i++]) break;
                    if (i == n) return idx - n + 1;
                }
            }
            idx++;
        }
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    fun findPattern(stream: InfiniteStream, pattern: IntArray): Int {
        val n = pattern.size
        val window = ArrayDeque<Int>()
        var idx = 0
        while (true) {
            val bit = stream.next()
            window.addLast(bit)
            if (window.size > n) window.removeFirst()
            if (window.size == n && window.toIntArray().contentEquals(pattern))
                return idx - n + 1
            idx++
        }
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution:
    def findPattern(self, stream: 'InfiniteStream', pattern: list[int]) -> int:
        n = len(pattern)
        window = []
        idx = 0
        while True:
            bit = stream.next()
            window.append(bit)
            if len(window) > n:
                window.pop(0)
            if len(window) == n and window == pattern:
                return idx - n + 1
            idx += 1
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

impl Solution {
    pub fn find_pattern(stream: &mut InfiniteStream, pattern: Vec<i32>) -> i32 {
        let n = pattern.len();
        let mut window = std::collections::VecDeque::new();
        let mut idx = 0;
        loop {
            let bit = stream.next();
            window.push_back(bit);
            if window.len() > n { window.pop_front(); }
            if window.len() == n && window.iter().copied().eq(pattern.iter().copied()) {
                return idx as i32 - n as i32 + 1;
            }
            idx += 1;
        }
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    findPattern(stream: InfiniteStream, pattern: number[]): number {
        const n = pattern.length;
        const window: number[] = [];
        let idx = 0;
        while (true) {
            const bit = stream.next();
            window.push(bit);
            if (window.length > n) window.shift();
            if (window.length === n && window.every((v, i) => v === pattern[i]))
                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 (≤ 100), since we compare the window to the pattern at each step.
  • 🧺 Space complexity: O(M), for the sliding window of pattern length.