3023. Find Pattern in Infinite Stream I
Problem Description
In this problem, we are given a binary array called pattern
and a class called InfiniteStream
which simulates an infinite stream of bits. The InfiniteStream
class has a function next()
that returns the next bit in the stream.
The goal is to return the first index (starting from 0
) of the infinite stream at which the given pattern
occurs. In other words, we want to find where the sequence of bits in pattern
matches the sequence of bits in the stream for the first time and return the starting index of that match in the stream. This is similar to finding a substring in an infinite string, where we are looking for a specific pattern of 0
s and 1
s.
Intuition
To find the pattern in the stream, we could brute force our way through the stream by constantly checking the pattern against the bits read from the stream. However, this approach can be very inefficient. With bit manipulation and a sliding window approach, we can solve the problem more elegantly and efficiently.
The intuition behind our solution is to think of the pattern
array and the current window of the stream of bits as binary numbers. As we read bits from the stream, we can shift these bits into two integers that represent the current window in the stream. By using two integers, we can handle patterns up to 100 bits long.
Once the current window reaches the length of the pattern, we check if the two binary numbers (divided between the two integers) match our pattern, also represented as two binary numbers. We keep track of the current window and the pattern using bit manipulation.
To do this, we split the pattern into two halves and convert each half into a binary number (a
for the first half and b
for the second half). We also maintain two integers (x
and y
) to represent the bits read from the stream for the current window. We apply a sliding window approach to read the stream, shift bits into our window, and compare against the binary number of the pattern. If we find a match, we return the starting index of the matching window.
Here's how we represent the pattern and the window as binary numbers:
- Split the pattern into two halves.
- Convert the first half into a binary number
a
. - Convert the second half into a binary number
b
. - As we read the stream, shift the bits into two binary numbers
x
(for the first half) andy
(for the second half). - Compare
x
toa
andy
tob
. If they match, return the starting index of the current window.
By comparing binary numbers instead of arrays of bits, we can efficiently determine if the pattern matches the current window of the stream.
Learn more about Sliding Window patterns.
Solution Approach
The solution uses bit manipulation and a sliding window approach to solve the problem in an efficient manner. Here is how the implementation works:
-
Convert Pattern to Binary Numbers: We first split the
pattern
into two parts - the left half and the right half. Then, we convert these halves into two binary numbers,a
for the left half andb
for the right half. To do this, we create bit masks (mask1
for the left half andmask2
for the right half) that will help us track which bits are relevant for each half. This way,a
andb
store the pattern to be matched in the stream as two separate integers. -
Reading the Stream: We initialize two integers:
x
andy
, which will keep track of the current window of bits from the stream. As we read the infinite stream usingstream.next()
, we shift the bits intoy
for the right half of the window. -
Extract and Move Bits: To maintain the connection between the two halves as we read new bits, we need to move the most significant bit of
y
intox
. Then, we shiftx
andy
to the left to prepare them for the next incoming bit from the stream. Masksmask1
andmask2
are used to keepx
andy
within the size of their respective halves. -
Check for Pattern Match: After every new bit is added to our window, if we have read at least as many bits as the pattern's length, we check if
a
equalsx
andb
equalsy
. If so, it indicates that we have found a match in the stream that starts fromi - m
, wherei
is the number of bits read andm
is the length of the pattern. -
Return the Index: As soon as a match is found, the starting index of this matching window is returned.
Here's a breakdown of the key statements in the solution implementation:
a |= pattern[i] << (half - 1 - i)
: Builds the binary number for the left half of the pattern (a
) using bit OR and shift operations.b |= pattern[i] << (m - 1 - i)
: Builds the binary number for the right half of the pattern (b
) using similar operations.v = y >> (m - half) & 1
: Extracts the most significant bit ofy
which is to be moved tox
.y &= mask2
: Applies the mask toy
to ensure it only contains bits from the right half of the pattern's length.x = x << 1 | v
: Shiftsx
to the left by one position and adds the extracted bit fromy
tox
.x &= mask1
: Applies the mask tox
to maintain the size of the left half.if i >= m and a == x and b == y: return i - m
: Ifx
andy
matcha
andb
respectively, and we have read enough bits, the starting index of the match is returned.
The use of bit manipulation and the sliding window technique allows us to efficiently look for the pattern match in an infinite stream without storing the stream's content, only keeping track of the current window and the pattern as integer representations.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach with a small example. Suppose we have a binary pattern [1, 0, 1]
we wish to find in an infinite stream of bits. Our InfiniteStream
class provides us with a next()
function that we call to get the next bit in the stream.
-
Convert Pattern to Binary Numbers:
- Given the pattern is
[1, 0, 1]
, let's consider it as a whole because it is short enough to fit into an integer. In a more complex variant, for a longer pattern, we would split it into two parts. Now,a
would represent this binary number, which equals1*2^2 + 0*2^1 + 1*2^0 = 5
.
- Given the pattern is
-
Reading the Stream:
- We begin with
a = 5
and initializex = 0
andy = 0
to keep track of bits from the stream. Suppose the first bits of the stream we read are1, 1, 1
, which do not match our pattern.
- We begin with
-
Extract and Move Bits:
- The stream bits are read one by one and pushed into
y
. As we don't need to split the pattern into halves here, we focus only ony
. After reading 3 bits from the stream1, 1, 1
,y
becomes1*2^2 + 1*2^1 + 1*2^0 = 7
.
- The stream bits are read one by one and pushed into
-
Check for Pattern Match:
- Once we have a window of bits equal to the pattern's length, we compare
y
toa
. Since5
does not equal7
, we do not have a match. We proceed to read the next bit in the stream, which is0
. - We shift
y
to the left and add the new bit:y = (7 << 1) | 0 = 14
. However, since our window size matches the pattern size, we remove the oldest bit, which requires us to masky
with111
or7
to keep only the last three bits. Nowy = 14 & 7 = 6
. Again,6
does not equal5
, so we move on to the next bit from the stream.
- Once we have a window of bits equal to the pattern's length, we compare
-
Return the Index:
- Reading the next bit,
1
, we would now havey = (6 << 1) | 1 = 13
. We apply the mask again:y = 13 & 7 = 5
. Nowy
equals5
, which is the same asa
. - Since
a
equalsy
, we have found the pattern starting from index3
of the stream (i.e., after the first three bits1, 1, 1
). So the first index of the pattern in the stream would be3
(considering the starting index is0
).
- Reading the next bit,
This small example demonstrates the core concept of using binary numbers to track the current window of bits from the stream and the pattern we're searching for. Bit manipulation allows efficient comparisons and updates, conducive to streams of potentially infinite length.
Solution Implementation
1# Let's assume we already have a definition for an infinite stream class.
2
3# This solution class defines a method that searches for a pattern in an infinite stream of bits.
4class Solution:
5 def find_pattern(self, stream, pattern):
6 # Initialize variables to store the pattern in two halves
7 upper_half_pattern = 0
8 lower_half_pattern = 0
9
10 # Calculate the length of the pattern
11 pattern_length = len(pattern)
12
13 # Find the middle of the pattern to split it into two halves
14 half_length = pattern_length >> 1
15
16 # Masks to extract the relevant bits of a given length
17 mask_upper_half = (1 << half_length) - 1
18 mask_lower_half = (1 << (pattern_length - half_length)) - 1
19
20 # Convert the first half of the pattern to a bit representation
21 for i in range(half_length):
22 upper_half_pattern |= pattern[i] << (half_length - 1 - i)
23
24 # Convert the second half of the pattern to a bit representation
25 for i in range(half_length, pattern_length):
26 lower_half_pattern |= pattern[i] << (pattern_length - 1 - i)
27
28 # Variables to track the current stream's half-patterns
29 upper_half_stream = 0
30 lower_half_stream = 0
31
32 # Iterate over the infinite stream
33 for i in itertools.count(1): # using count method from itertools to create an infinite loop
34 # Fetch the next value from the stream
35 value = stream.next()
36
37 # Update the lower half's bit representation with the new value
38 lower_half_stream = (lower_half_stream << 1) | value
39
40 # Extract the bit to shift into the upper half
41 value = (lower_half_stream >> (pattern_length - half_length)) & 1
42
43 # Keep only the relevant bits in the lower half
44 lower_half_stream &= mask_lower_half
45
46 # Update the upper half's bit representation with the carried over bit
47 upper_half_stream = (upper_half_stream << 1) | value
48
49 # Keep only the relevant bits in the upper half
50 upper_half_stream &= mask_upper_half
51
52 # Check if the current half-patterns match the target patterns and the pattern is complete
53 if i >= pattern_length and upper_half_pattern == upper_half_stream and lower_half_pattern == lower_half_stream:
54 # Return the index at which the end of the pattern was found
55 return i - pattern_length
56
57# Note: This code assumes that the stream is an infinite source of bits and the 'stream.next()'
58# method to be defined that returns the next bit from the stream as an integer (either 0 or 1).
59# Additionally, the input 'Optional["InfiniteStream"]' has been simplified to 'stream' for clarity.
60
1class Solution {
2
3 /**
4 * Searches an infinite stream for a given pattern.
5 * @param infiniteStream The source of data as an infinite stream of bits.
6 * @param pattern The pattern of bits to be found in the stream.
7 * @return The starting index of the first occurrence of the pattern.
8 */
9 public int findPattern(InfiniteStream infiniteStream, int[] pattern) {
10 // Initialize variables to hold the hashed patterns and stream bits.
11 long patternHashPart1 = 0, patternHashPart2 = 0;
12 int patternLength = pattern.length;
13 int halfPatternLength = patternLength >> 1; // equivalent to division by 2 using bit shift.
14 // Create masks to limit the hash size to the pattern's length.
15 long maskPart1 = (1L << halfPatternLength) - 1;
16 long maskPart2 = (1L << (patternLength - halfPatternLength)) - 1;
17
18 // Hash the pattern into two parts. This is done for optimizing the matching process.
19 for (int i = 0; i < halfPatternLength; ++i) {
20 patternHashPart1 |= (long) pattern[i] << (halfPatternLength - 1 - i);
21 }
22 for (int i = halfPatternLength; i < patternLength; ++i) {
23 patternHashPart2 |= (long) pattern[i] << (patternLength - 1 - i);
24 }
25
26 // Initialize variables to track the current hashed stream.
27 long currentHashPart1 = 0, currentHashPart2 = 0;
28 // Start reading bits from the stream.
29 for (int i = 1;; ++i) {
30 int bit = infiniteStream.next();
31 currentHashPart2 = currentHashPart2 << 1 | bit;
32 bit = (int) ((currentHashPart2 >> (patternLength - halfPatternLength)) & 1);
33 currentHashPart2 &= maskPart2;
34 currentHashPart1 = currentHashPart1 << 1 | bit;
35 currentHashPart1 &= maskPart1;
36
37 // If the current stream hash matches the pattern hash, return the starting index.
38 if (i >= patternLength && patternHashPart1 == currentHashPart1 && patternHashPart2 == currentHashPart2) {
39 return i - patternLength;
40 }
41 }
42 }
43}
44
1class Solution {
2public:
3 // Takes a stream and a pattern to find the pattern's first occurrence in the stream
4 int findPattern(InfiniteStream* stream, vector<int>& pattern) {
5 // Initialize variables to store the binary representation of the pattern
6 long long pattern_upper_half = 0, pattern_lower_half = 0;
7 int pattern_length = pattern.size();
8 int half_length = pattern_length >> 1; // Equivalent to dividing by 2 using bitwise operation
9
10 // Bit masks to isolate relevant bits after shifting
11 long long mask_upper_half = (1LL << half_length) - 1;
12 long long mask_lower_half = (1LL << (pattern_length - half_length)) - 1;
13
14 // Store the upper and lower parts of the pattern
15 for (int i = 0; i < half_length; ++i) {
16 pattern_upper_half |= (long long) pattern[i] << (half_length - 1 - i);
17 }
18 for (int i = half_length; i < pattern_length; ++i) {
19 pattern_lower_half |= (long long) pattern[i] << (pattern_length - 1 - i);
20 }
21
22 // Initialize variables to store the current state of the stream
23 long long stream_upper_half = 0, stream_lower_half = 0;
24 // Loop through the stream until the pattern is found
25 for (int i = 1;; ++i) { // Infinite loop, will return once pattern is found
26 int bit = stream->next(); // Get the next bit from the stream
27 stream_lower_half = stream_lower_half << 1 | bit; // Shift in the new bit
28 bit = (int) ((stream_lower_half >> (pattern_length - half_length)) & 1); // Get corresponding upper half bit
29 stream_lower_half &= mask_lower_half; // Apply mask to maintain relevant bits
30 stream_upper_half = stream_upper_half << 1 | bit; // Shift in the new bit to upper half
31 stream_upper_half &= mask_upper_half; // Apply mask to maintain relevant bits
32
33 // If the current stream state matches the pattern and we have read enough bits
34 if (i >= pattern_length && pattern_upper_half == stream_upper_half && pattern_lower_half == stream_lower_half) {
35 // Return the start position of the pattern in the stream
36 return i - pattern_length;
37 }
38 }
39 }
40};
41
1// Define the InfiniteStream interface with a method next that returns the next bit
2interface InfiniteStream {
3 next(): number;
4}
5
6// Takes a stream and a pattern to find the pattern's first occurrence in the stream
7function findPattern(stream: InfiniteStream, pattern: number[]): number {
8 // Initialize variables to represent the binary representation of the pattern
9 let patternUpperHalf = 0n, patternLowerHalf = 0n;
10 const patternLength = pattern.length;
11 const halfLength = patternLength >> 1; // Divide by 2 using bitwise operation
12
13 // Bit masks to isolate relevant bits after shifting
14 const maskUpperHalf = (1n << BigInt(halfLength)) - 1n;
15 const maskLowerHalf = (1n << BigInt(patternLength - halfLength)) - 1n;
16
17 // Store the upper and lower parts of the pattern as binary values
18 for (let i = 0; i < halfLength; ++i) {
19 patternUpperHalf |= BigInt(pattern[i]) << BigInt(halfLength - 1 - i);
20 }
21 for (let i = halfLength; i < patternLength; ++i) {
22 patternLowerHalf |= BigInt(pattern[i]) << BigInt(patternLength - 1 - i);
23 }
24
25 // Initialize variables to store the current binary representation of the stream
26 let streamUpperHalf = 0n, streamLowerHalf = 0n;
27
28 // Loop through the stream until the pattern is found
29 for (let i = 1; ; ++i) { // Infinite loop, the function will return once the pattern is found
30 const bit = stream.next(); // Get the next bit from the stream
31 streamLowerHalf = (streamLowerHalf << 1n) | BigInt(bit); // Shift in the new bit
32
33 // Get the corresponding upper half bit
34 const upperBit = Number((streamLowerHalf >> BigInt(patternLength - halfLength)) & 1n);
35
36 // Apply masks to maintain relevant bits
37 streamLowerHalf &= maskLowerHalf;
38 streamUpperHalf = (streamUpperHalf << 1n) | BigInt(upperBit);
39 streamUpperHalf &= maskUpperHalf;
40
41 // If the current stream state matches the pattern and we have read enough bits
42 if (i >= patternLength && patternUpperHalf === streamUpperHalf && patternLowerHalf === streamLowerHalf) {
43 // Return the start position of the pattern in the stream
44 return i - patternLength;
45 }
46 }
47}
48
Time and Space Complexity
The time complexity of the provided code snippet is O(n)
, where n
is the length of the data stream until a match is found for the pattern
. This is because the code examines each value of the stream only once in a linear fashion until the pattern
is found, and the comparisons within each iteration are done in constant time.
The space complexity of the code is O(1)
. The code uses a fixed number of variables (a
, b
, x
, y
, mask1
, mask2
, v
, and i
) that do not grow with the size of the input (stream or the pattern
). Therefore, no matter how long the stream is or what the size of the pattern (m
) is, the amount of memory used does not increase with n
or m
.
Learn more about how to find time and space complexity quickly using problem constraints.
What is the best way of checking if an element exists in a sorted array once in terms of time complexity? Select the best that applies.
Recommended Readings
https algomonster s3 us east 2 amazonaws com cover_photos stack svg Sliding Window Maximum Monotonic Stack We have an array and a sliding window defined by a start index and an end index The sliding window moves from left of the array to right There are always k elements in
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!