Find Pattern in Infinite Stream II - Practice Coding Problems

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

Note: You can only read each bit from the stream once, and you cannot go back to re-read previous bits.

Input & Output

Example 1 — Basic Pattern Match

$ Input: pattern = [1,0], stream = [0,1,0,1,...]

› Output: 1

💡 Note: Pattern [1,0] first appears at index 1 in the stream: [0,1,0,1,...]. The bits at positions 1 and 2 are [1,0].

Example 2 — Pattern at Start

$ Input: pattern = [1,1], stream = [1,1,0,1,1,...]

› Output: 0

💡 Note: Pattern [1,1] appears immediately at the beginning of the stream at index 0.

Example 3 — Longer Pattern

$ Input: pattern = [0,0,1], stream = [1,0,0,1,0,0,0,1,...]

› Output: 1

💡 Note: Pattern [0,0,1] first appears at index 1: stream positions 1,2,3 contain [0,0,1].

Constraints

1 ≤ pattern.length ≤ 10⁴
pattern[i] is either 0 or 1
stream consists only of 0s and 1s
stream is guaranteed to contain the pattern

Visualization

Tap to expand

Understanding the Visualization

Input

Binary pattern and infinite stream of bits

Process

Read bits sequentially and match against pattern

Output

First index where pattern matches completely

Key Takeaway

🎯 Key Insight: Use KMP or rolling hash to avoid re-reading bits when pattern mismatches occur

Asked in

G Google 35 f Facebook 28 a Amazon 22 M Microsoft 18

The key insight is to use efficient string matching algorithms like KMP or rolling hash since we can only read each bit once. The optimal approach uses KMP algorithm for O(n + m) time complexity where n is the number of bits read and m is pattern length. Time: O(n + m), Space: O(m).

Common Approaches

Approach	Time	Space	Notes
✓ Sliding Window with KMP	O(n + m)	O(m)	Use KMP algorithm to avoid redundant comparisons when mismatches occur
Rolling Hash	O(n + m)	O(m)	Use rolling hash for O(1) pattern comparison at each position
Brute Force with Buffer	O(n × m)	O(m)	Keep a buffer of recent bits and check pattern match at every position

Sliding Window with KMP — Algorithm Steps

Build KMP failure function for the pattern
Read stream bits one by one
Use failure function to determine how far back to check on mismatch
Continue until pattern is found

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Failure

Create failure function array

Match/Skip

Use failure function on mismatch

Found

Pattern matched completely

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    int* bits;
    int size;
    int index;
} InfiniteStream;

InfiniteStream* createStream(int* bits, int size) {
    InfiniteStream* stream = malloc(sizeof(InfiniteStream));
    stream->bits = bits;
    stream->size = size;
    stream->index = 0;
    return stream;
}

int next(InfiniteStream* stream) {
    int bit = stream->bits[stream->index % stream->size];
    stream->index++;
    return bit;
}

int* buildFailureFunction(int* pattern, int patternSize) {
    int* failure = malloc(patternSize * sizeof(int));
    failure[0] = 0;
    int j = 0;
    
    for (int i = 1; i < patternSize; i++) {
        while (j > 0 && pattern[i] != pattern[j]) {
            j = failure[j - 1];
        }
        if (pattern[i] == pattern[j]) {
            j++;
        }
        failure[i] = j;
    }
    return failure;
}

int solution(int* pattern, int patternSize, InfiniteStream* stream) {
    if (patternSize == 0) return 0;
    
    int* failure = buildFailureFunction(pattern, patternSize);
    int j = 0; // Pattern index
    int i = 0; // Stream index
    
    while (1) {
        int bit = next(stream);
        
        while (j > 0 && bit != pattern[j]) {
            j = failure[j - 1];
        }
        
        if (bit == pattern[j]) {
            j++;
        }
        
        if (j == patternSize) {
            free(failure);
            return i - patternSize + 1;
        }
        
        i++;
    }
}

Time & Space Complexity

Time Complexity

⏱️

O(n + m)

Each stream bit is processed exactly once, plus O(m) to build failure function

✓ Linear Growth

Space Complexity

O(m)

Failure function array stores m values where m is pattern length

✓ Linear Space

23.4K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Sliding Window with KMP — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler