Skip to main content
Talentd

Find Pattern in Infinite Stream I - Solution & Explanation

MediumPremiumFree on FleetCodeArraySliding WindowRolling HashString Matching8 min readAsked at: Uber
Practice this problem

Problem Statement

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

 

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 <= 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.

Approach Overview

Problem Overview: You receive bits from an infinite stream one at a time and must detect when a given binary pattern appears. The stream never ends, so you cannot store the entire input. The goal is to continuously read values and determine whether the last m bits match the target pattern.

Approach 1: Brute Force Stream Comparison (O(n * m) time, O(m) space)

The simplest idea stores the last m values from the stream and compares them to the pattern after each new bit arrives. Maintain a buffer of size m. Every time you call next(), shift the window and perform an element‑by‑element comparison against the pattern array. This works but each check costs O(m), making the overall complexity O(n * m) for n processed bits. The approach demonstrates the core sliding window idea but is inefficient for large patterns.

Approach 2: Rolling Hash / String Matching (O(n) time, O(1) space)

Instead of comparing the whole window each time, treat the pattern as a binary number and maintain a rolling hash for the last m bits of the stream. Each new bit shifts the previous hash left and inserts the new value, while masking out bits that fall outside the window. This technique is similar to string matching algorithms such as Rabin–Karp. Because the update takes constant time and comparison is a single integer equality check, the stream can be processed in O(n) time with O(1) extra memory.

Approach 3: Bit Manipulation + Sliding Window (O(n) time, O(1) space)

The optimal implementation uses bit manipulation to maintain a compact representation of the current window. Convert the pattern into an integer mask. While reading bits from the stream, maintain a rolling integer window: window = ((window << 1) | bit) & maskLimit. The mask trims the window to exactly m bits. When window == patternMask, the pattern has appeared in the stream. This approach combines array processing with a sliding window and bitwise operations, giving constant memory and extremely fast updates.

Recommended for interviews: Interviewers expect the bit manipulation sliding window solution. Starting with the brute force buffer comparison shows you understand the streaming constraint, but the optimized rolling window demonstrates strong knowledge of hashing and windowed pattern matching in continuous data streams.

Solution

We notice that the length of the array pattern does not exceed 100, therefore, we can use two 64-bit integers a and b to represent the binary numbers of the left and right halves of pattern.

Next, we traverse the data stream, also maintaining two 64-bit integers x and y to represent the binary numbers of the current window of the length of pattern. If the current length reaches the window length, we compare whether a and x are equal, and whether b and y are equal. If they are, we return the index of the current data stream.

The time complexity is O(n + m), where n and m are the number of elements in the data stream and pattern respectively. The space complexity is O(1).

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Window ComparisonO(n * m)O(m)Good for understanding the streaming constraint and initial brute force logic.
Rolling Hash (Rabin–Karp style)O(n)O(1)Efficient pattern detection in streaming or substring search problems.
Bit Manipulation + Sliding WindowO(n)O(1)Optimal for binary streams where the pattern length is small enough to fit in an integer mask.

Video Solution

3023. Find Pattern in Infinite Stream I (Leetcode Medium) • Programming Live with Larry • 363 views views

Frequently Asked Questions

Is Find Pattern in Infinite Stream I easy or hard?
Find Pattern in Infinite Stream I is rated Medium difficulty on LeetCode. The challenge comes from handling an infinite stream without storing all elements. Recognizing that a sliding window with bit manipulation can represent the last m bits efficiently makes the problem straightforward.
Find Pattern in Infinite Stream I Python/Java solution
Implementations typically convert the pattern into a binary integer and maintain a rolling window while calling the stream API. Python, Java, C++, and Go solutions all follow the same idea: shift the window left, add the new bit, mask excess bits, and compare with the pattern mask.
How to solve Find Pattern in Infinite Stream I in O(n)?
Maintain a sliding window represented as an integer bitmask. Convert the pattern to an integer mask and update the current window using left shift and bitwise OR when reading each new bit from the stream. Apply a mask to keep only the last m bits, then compare the window with the pattern mask. This processes each stream element once.
What is the best approach for Find Pattern in Infinite Stream I?
The most efficient approach uses bit manipulation with a sliding window. Convert the pattern into a binary mask and maintain a rolling window of the last m bits from the stream. Each new bit updates the window using bit shifts and masking, allowing constant-time comparison. This achieves O(n) time and O(1) space.
Is Find Pattern in Infinite Stream I asked at Google/Amazon/Meta?
Streaming pattern detection problems are common in interviews at companies like Google, Amazon, and Meta because they test sliding window logic, bit manipulation, and real-time data processing. Variants of this problem often appear when discussing stream processing or substring search algorithms.
What data structure is used in Find Pattern in Infinite Stream I?
The solution primarily uses a sliding window represented by an integer bitmask. Instead of storing an array window, bit manipulation compresses the last m bits into a single integer. This approach acts like a rolling hash and avoids extra memory usage.
What is the time complexity of Find Pattern in Infinite Stream I?
The optimal solution runs in O(n) time, where n is the number of bits processed from the stream until the pattern is detected. Each incoming bit updates a rolling window using constant-time bit operations. Space complexity remains O(1) because only a few integers are stored.

Ready to solve this problem?

Practice Find Pattern in Infinite Stream I with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays