Find Pattern in Infinite Stream II - Solution & Explanation

Q: Is Find Pattern in Infinite Stream II easy or hard?

Find Pattern in Infinite Stream II is classified as a Hard problem because it combines streaming constraints with string matching techniques. Recognizing that rolling hash or similar pattern matching algorithms can be adapted to an infinite stream is the main challenge.

Q: Find Pattern in Infinite Stream II Python/Java solution

Python, Java, C++, and Go implementations follow the same idea: maintain a window of size m and update a rolling hash as new elements arrive from the stream API. Once the rolling hash equals the pattern hash, perform a direct comparison and return the starting index.

Q: How to solve Find Pattern in Infinite Stream II in O(n)?

Use a Rabin–Karp style rolling hash. Precompute the hash of the pattern, maintain a window of size m over the stream, and update the hash when sliding the window by removing the old value and adding the new one. When the hashes match, compare the window and pattern to confirm. Each stream element is processed once, giving O(n) time.

Q: What is the best approach for Find Pattern in Infinite Stream II?

The most efficient approach uses a rolling hash (Rabin–Karp) with a sliding window over the stream. Compute the hash of the pattern, then update the window hash each time a new element arrives from the stream. Matching hashes trigger a verification check. This runs in O(n) time with O(m) space where m is the pattern length.

Q: Is Find Pattern in Infinite Stream II asked at Google/Amazon/Meta?

Pattern matching in streams and rolling hash techniques appear frequently in interviews at companies like Google, Amazon, and Meta. Variants involving Rabin–Karp, KMP, or sliding windows over streaming data are common system-style algorithm questions.

Q: What data structure is used in Find Pattern in Infinite Stream II?

The solution typically uses a fixed-size sliding window buffer (array or deque) to store the last m elements from the stream. A rolling hash value is maintained alongside it to enable constant-time updates as the window moves.

Q: What is the time complexity of Find Pattern in Infinite Stream II?

The optimal rolling hash solution runs in O(n) time where n is the number of stream elements processed until the pattern appears. Each step updates the hash in O(1). The space complexity is O(m) because only the current window of size m must be stored.

HardPremiumFree on FleetCodeArray Sliding Window Rolling Hash String Matching3 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 <= 10⁴
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 10⁵ bits of the stream.

Approach Overview

Problem Overview: You receive numbers from an infinite stream through an API like next(). Given a finite pattern array, return the first index where this pattern appears in the stream. Since the stream is unbounded, you cannot store everything; the algorithm must process elements incrementally and detect the match as soon as the pattern appears.

Approach 1: Brute Force Sliding Window (O(n * m) time, O(m) space)

The direct approach keeps a window of the last m elements, where m is the pattern length. Each time you read a new value from the stream, append it to the window and compare the entire window with the pattern element by element. If they match, return the starting index. Otherwise shift the window by one and repeat. This uses a simple sliding window buffer but performs a full comparison for every step, which makes it inefficient when the stream runs for a long time before the pattern appears.

Approach 2: Rolling Hash (Rabin–Karp) (O(n) time, O(m) space)

A faster solution treats the pattern matching task as a streaming version of classic string matching. Precompute a hash for the pattern. While reading elements from the stream, maintain a rolling hash for the current window of size m. Each new element updates the hash by removing the contribution of the outgoing element and adding the new one. If the rolling hash equals the pattern hash, verify the window to avoid collisions. This avoids repeated full comparisons and turns the search into near linear time.

The rolling hash relies on a polynomial hash or modular base exponentiation from the hash function family. Because the window moves one element at a time, updating the hash costs O(1). The algorithm stores only the current window and a few hash parameters, which keeps memory bounded even though the stream is infinite.

Recommended for interviews: The rolling hash (Rabin–Karp) solution is the expected approach. The brute force sliding window shows you understand the streaming constraint, but the optimized hashing approach demonstrates knowledge of string matching algorithms and efficient incremental computation. Interviewers look for the ability to process unbounded input while maintaining O(1) update work per element.

Solutions for this problem are being prepared.

Try solving it yourself

Detailed Complexity Analysis

Approach	Time	Space	When to Use
Brute Force Sliding Window	O(n * m)	O(m)	Simple implementation or when pattern length is very small
Rolling Hash (Rabin–Karp)	O(n)	O(m)	General case for large streams where efficient incremental matching is required

Video Solution

3037. Find Pattern in Infinite Stream II (Leetcode Hard) • Programming Live with Larry • 208 views views

Frequently Asked Questions

Is Find Pattern in Infinite Stream II easy or hard?

Find Pattern in Infinite Stream II is classified as a Hard problem because it combines streaming constraints with string matching techniques. Recognizing that rolling hash or similar pattern matching algorithms can be adapted to an infinite stream is the main challenge.

Find Pattern in Infinite Stream II Python/Java solution

Python, Java, C++, and Go implementations follow the same idea: maintain a window of size m and update a rolling hash as new elements arrive from the stream API. Once the rolling hash equals the pattern hash, perform a direct comparison and return the starting index.

How to solve Find Pattern in Infinite Stream II in O(n)?

Use a Rabin–Karp style rolling hash. Precompute the hash of the pattern, maintain a window of size m over the stream, and update the hash when sliding the window by removing the old value and adding the new one. When the hashes match, compare the window and pattern to confirm. Each stream element is processed once, giving O(n) time.

What is the best approach for Find Pattern in Infinite Stream II?

The most efficient approach uses a rolling hash (Rabin–Karp) with a sliding window over the stream. Compute the hash of the pattern, then update the window hash each time a new element arrives from the stream. Matching hashes trigger a verification check. This runs in O(n) time with O(m) space where m is the pattern length.

Is Find Pattern in Infinite Stream II asked at Google/Amazon/Meta?

Pattern matching in streams and rolling hash techniques appear frequently in interviews at companies like Google, Amazon, and Meta. Variants involving Rabin–Karp, KMP, or sliding windows over streaming data are common system-style algorithm questions.

What data structure is used in Find Pattern in Infinite Stream II?

The solution typically uses a fixed-size sliding window buffer (array or deque) to store the last m elements from the stream. A rolling hash value is maintained alongside it to enable constant-time updates as the window moves.

What is the time complexity of Find Pattern in Infinite Stream II?

The optimal rolling hash solution runs in O(n) time where n is the number of stream elements processed until the pattern appears. Each step updates the hash in O(1). The space complexity is O(m) because only the current window of size m must be stored.

Ready to solve this problem?

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

Practice on FleetCode

Number of Integers With Popcount-Depth Equal to K I

Problem Info

DifficultyHard

Acceptance67.5%

Approaches0

Reading time3 min

Asked at

Uber