3023. Find Pattern in Infinite Stream I

MediumArrayString MatchingSliding WindowHash FunctionRolling Hash

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 0s and 1s.

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) and y (for the second half).
Compare x to a and y to b. 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 and b for the right half. To do this, we create bit masks (mask1 for the left half and mask2 for the right half) that will help us track which bits are relevant for each half. This way, a and b store the pattern to be matched in the stream as two separate integers.
Reading the Stream: We initialize two integers: x and y, which will keep track of the current window of bits from the stream. As we read the infinite stream using stream.next(), we shift the bits into y 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 into x. Then, we shift x and y to the left to prepare them for the next incoming bit from the stream. Masks mask1 and mask2 are used to keep x and y 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 equals x and b equals y. If so, it indicates that we have found a match in the stream that starts from i - m, where i is the number of bits read and m 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 of y which is to be moved to x.
y &= mask2: Applies the mask to y to ensure it only contains bits from the right half of the pattern's length.
x = x << 1 | v: Shifts x to the left by one position and adds the extracted bit from y to x.
x &= mask1: Applies the mask to x to maintain the size of the left half.
if i >= m and a == x and b == y: return i - m: If x and y match a and b 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 Evaluator

Example 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 equals 1*2^2 + 0*2^1 + 1*2^0 = 5.
Reading the Stream:
- We begin with a = 5 and initialize x = 0 and y = 0 to keep track of bits from the stream. Suppose the first bits of the stream we read are 1, 1, 1, which do not match our pattern.
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 on y. After reading 3 bits from the stream 1, 1, 1, y becomes 1*2^2 + 1*2^1 + 1*2^0 = 7.
Check for Pattern Match:
- Once we have a window of bits equal to the pattern's length, we compare y to a. Since 5 does not equal 7, we do not have a match. We proceed to read the next bit in the stream, which is 0.
- 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 mask y with 111 or 7 to keep only the last three bits. Now y = 14 & 7 = 6. Again, 6 does not equal 5, so we move on to the next bit from the stream.
Return the Index:
- Reading the next bit, 1, we would now have y = (6 << 1) | 1 = 13. We apply the mask again: y = 13 & 7 = 5. Now y equals 5, which is the same as a.
- Since a equals y, we have found the pattern starting from index 3 of the stream (i.e., after the first three bits 1, 1, 1). So the first index of the pattern in the stream would be 3 (considering the starting index is 0).

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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

How does merge sort divide the problem into subproblems?

Divide the array into two equal halves by index

Divide the array into two based on whether an element is smaller than an arbitrary value

Divide the array into a stray element and the rest of the array

Merge sort does not use divide and conquer

I don’t know