Problem Description

You have an infinite stream of binary bits (0s and 1s) and need to find where a specific pattern first appears in this stream.

Given:

• A binary array pattern containing only 0s and 1s
• An InfiniteStream object that provides access to an infinite sequence of bits
• The stream has a next() method that returns one bit at a time

Your task is to find the first starting index where the pattern matches consecutive bits in the stream.

For example, if pattern = [1, 0] and the stream produces [0, 1, 0, 1, ...], the pattern first matches at index 1 (the subsequence [1, 0] starting at position 1).

The solution uses bit manipulation to efficiently compare patterns. Since the pattern length is at most 100, it splits the pattern into two halves and represents each half as a 64-bit integer (a and b). As bits are read from the stream, it maintains a sliding window represented by two corresponding integers (x and y). When the window size matches the pattern length, it checks if both halves match. If they do, it returns the starting index of the match.

The key insight is using bit operations for fast pattern matching:

• Left shift operations (<<) to build binary representations
• Bitwise OR (|) to set specific bits
• Bitwise AND (&) with masks to maintain fixed-width windows
• Direct integer comparison for pattern matching

Intuition

The straightforward approach would be to read bits one by one and check if the last m bits match the pattern every time we read a new bit. However, comparing arrays element by element repeatedly would be inefficient.

The key observation is that we can treat the pattern as a binary number. For instance, pattern [1, 0, 1] can be represented as the binary number 101. This transforms our pattern matching problem into a number comparison problem - we just need to check if the current window of bits equals our pattern when interpreted as a number.

Why split into two halves? Since the pattern can be up to 100 bits long, it exceeds what a single 64-bit integer can hold. By splitting the pattern into two parts, we ensure each part fits within a 64-bit integer. The left half goes into integer a, and the right half goes into integer b.

As we read the stream bit by bit, we maintain a sliding window of the same size as our pattern. This window is also represented as two integers (x and y). Each new bit shifts our window:

• The new bit enters from the right
• The oldest bit falls off from the left
• We use bit masks (mask1 and mask2) to ensure our window integers don't grow beyond their designated sizes

The beauty of this approach is that pattern matching becomes a simple integer comparison: if a == x and b == y, we've found our match. This is much faster than comparing arrays element by element, as we're leveraging the CPU's ability to compare integers in a single operation.

The bit manipulation operations (<<, |, &) allow us to efficiently update our sliding window and maintain the binary representation, turning what could be an O(m) comparison at each step into an O(1) operation.

Learn more about Sliding Window patterns.

Solution Approach

The implementation uses bit manipulation with a sliding window technique to efficiently find the pattern in the stream.

Step 1: Split and Convert Pattern to Binary Numbers

Since the pattern can be up to 100 bits (exceeding 64-bit integer capacity), we split it into two halves:

• half = m >> 1 calculates the midpoint using right shift (equivalent to m // 2)
• First half (indices 0 to half-1) is stored in integer a
• Second half (indices half to m-1) is stored in integer b

For each half, we build the binary representation:

for i in range(half):
    a |= pattern[i] << (half - 1 - i)

This places each bit at its correct position. For example, if pattern's first half is [1, 0, 1], we get a = 101 in binary.

Step 2: Create Bit Masks

We create masks to ensure our sliding window integers stay within bounds:

• mask1 = (1 << half) - 1 creates a mask with half ones (e.g., for half=3, mask1 = 0b111)
• mask2 = (1 << (m - half)) - 1 creates a mask for the second half

Step 3: Process Stream with Sliding Window

Initialize window integers x = 0 and y = 0, then for each bit from the stream:

1. Read the next bit: v = stream.next()
2. Update the right window (y):
   • Shift left and add new bit: y = y << 1 | v
   • Extract overflow bit for left window: v = y >> (m - half) & 1
   • Keep only valid bits: y &= mask2
3. Update the left window (x):
   • Shift left and add overflow from y: x = x << 1 | v
   • Keep only valid bits: x &= mask1

Step 4: Check for Pattern Match

Once we've read at least m bits (i >= m), we check if both halves match:

• If a == x and b == y, we found the pattern
• Return i - m as the starting index (current position minus pattern length)

The algorithm continues reading bits until a match is found. The count(1) creates an infinite counter starting from 1, tracking our position in the stream.

This approach achieves O(1) comparison per bit read, making it highly efficient compared to naive array comparison which would be O(m) per position.

Example Walkthrough

Let's trace through finding pattern [1, 0, 1] in a stream that produces [0, 1, 0, 1, 1, ...].

Setup Phase:

• Pattern length m = 3
• Split point: half = 3 >> 1 = 1 (first half has 1 bit, second half has 2 bits)
• Convert first half [1] to integer a:
  • a = 0
  • a |= 1 << (1-1-0) = 1 << 0 = 1
  • Result: a = 1
• Convert second half [0, 1] to integer b:
  • b = 0
  • b |= 0 << (2-1-0) = 0 << 1 = 0 → b = 0
  • b |= 1 << (2-1-1) = 1 << 0 = 1 → b = 1
  • Result: b = 1 (binary: 01)
• Create masks:
  • mask1 = (1 << 1) - 1 = 1 (binary: 1)
  • mask2 = (1 << 2) - 1 = 3 (binary: 11)

Stream Processing:

Position 1: Read bit 0

• Update y: y = 0 << 1 | 0 = 0
• Overflow to x: v = 0 >> 2 & 1 = 0
• Update x: x = 0 << 1 | 0 = 0
• Window: x=0, y=0 (represents [0])
• No check yet (need 3 bits)

Position 2: Read bit 1

• Update y: y = 0 << 1 | 1 = 1
• Overflow: v = 1 >> 2 & 1 = 0
• Update x: x = 0 << 1 | 0 = 0
• Window: x=0, y=1 (represents [0, 1])
• No check yet

Position 3: Read bit 0

• Update y: y = 1 << 1 | 0 = 2 (binary: 10)
• Overflow: v = 2 >> 2 & 1 = 0
• Update x: x = 0 << 1 | 0 = 0
• Window: x=0, y=2 (represents [0, 1, 0])
• Check: a=1 ≠ x=0 - no match

Position 4: Read bit 1

• Update y: y = 2 << 1 | 1 = 5 (binary: 101)
• Overflow: v = 5 >> 2 & 1 = 1
• Apply mask to y: y = 5 & 3 = 1 (keeps last 2 bits: 01)
• Update x: x = 0 << 1 | 1 = 1
• Apply mask to x: x = 1 & 1 = 1
• Window: x=1, y=1 (represents [1, 0, 1])
• Check: a=1 == x=1 AND b=1 == y=1 - Match found!
• Return: 4 - 3 = 1 (starting index)

The pattern [1, 0, 1] first appears at index 1 in the stream, matching the subsequence at positions 1, 2, and 3.

Solution Implementation

Time and Space Complexity

The time complexity is O(n + m), where n is the number of elements read from the infinite stream until the pattern is found, and m is the length of the pattern.

Breaking down the time complexity:

• The first loop iterates half times, which is O(m/2) = O(m)
• The second loop iterates m - half times, which is also O(m/2) = O(m)
• The main loop reads from the stream and performs constant-time bitwise operations for each element until the pattern is found, taking O(n) time
• Total: O(m) + O(m) + O(n) = O(n + m)

The space complexity is O(1) because:

• The algorithm uses a fixed number of integer variables (a, b, m, half, mask1, mask2, x, y, i, v)
• These variables store bit-packed representations of the pattern halves and sliding windows
• The space used does not grow with the input size, as the bit operations ensure the values stay within fixed bounds determined by the masks
• Even though the pattern has length m, it's already provided as input and the algorithm only uses constant additional space to process it

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Bit Positioning When Building Pattern Representation

A common mistake is placing bits in the wrong positions when converting the pattern array to integers. Many developers might write:

# WRONG: This reverses the bit order
for i in range(half_length):
    pattern_first_half |= pattern[i] << i  # Places first bit at position 0

This would represent pattern [1, 0, 1] as 0b101 with the first element at the least significant bit, when it should be at the most significant bit within the window.

Solution: Always place bits from left to right (most significant to least significant):

# CORRECT: Maintains proper bit order
for i in range(half_length):
    pattern_first_half |= pattern[i] << (half_length - 1 - i)

2. Off-by-One Error in Index Calculation

The code uses count(1) which starts counting from 1, but many might use count(0) or a manual counter starting from 0, leading to incorrect index calculations:

# WRONG: Using 0-based position counter
for position in count(0):  # or position = 0
    # ... process bit ...
    if position >= pattern_length - 1:  # Wrong adjustment
        if matches:
            return position - pattern_length + 1  # Incorrect formula

Solution: Be consistent with your indexing. If using 1-based counting (as in the solution), the return statement should be position - pattern_length. If using 0-based counting, adjust all related calculations accordingly.

3. Forgetting to Apply Masks After Bit Operations

Without applying masks, the integers can grow beyond their intended bit width:

# WRONG: Missing mask application
stream_second_half = (stream_second_half << 1) | current_bit
# stream_second_half can now have more bits than needed

This causes incorrect pattern matching as extra bits contaminate the comparison.

Solution: Always apply masks after shifting operations:

# CORRECT: Apply mask to maintain fixed width
stream_second_half = (stream_second_half << 1) | current_bit
stream_second_half &= second_half_mask  # Keep only relevant bits

4. Incorrect Overflow Bit Extraction

When extracting the overflow bit from the second half to feed into the first half, using the wrong bit position is a common error:

# WRONG: Extracting from wrong position
overflow_bit = stream_second_half >> pattern_length & 1  # Wrong shift amount

Solution: Extract from the correct position based on the second half's length:

# CORRECT: Extract the bit that would overflow
overflow_bit = (stream_second_half >> (pattern_length - half_length)) & 1

5. Premature Pattern Checking

Checking for pattern match before reading enough bits from the stream:

# WRONG: Checking too early
for position in count(1):
    # ... update buffers ...
    if pattern_first_half == stream_first_half:  # Might check with incomplete data
        return position - pattern_length

Solution: Only check for matches after reading at least pattern_length bits:

# CORRECT: Wait until window is full
if position >= pattern_length:
    if pattern_first_half == stream_first_half and pattern_second_half == stream_second_half:
        return position - pattern_length