Find Pattern in Infinite Stream I

Medium

Asked by:

11 views

Topics:

Strings

You are given a potentially infinite stream of characters arriving one at a time. You are also given a specific pattern (a string) that you need to detect within this stream.

Design an algorithm to efficiently detect the presence of the pattern in the stream. You should output true as soon as the pattern is detected, and false otherwise. Assume you can only store a limited number of characters from the stream at any given time.

Example 1:

Stream: a b a b c a b a a b c a b a b
Pattern: a b a b
Output: true
Explanation: "a b a b" is detected at the end of the stream.

Example 2:

Stream: a b c d e f g
Pattern: a b a
Output: false
Explanation: "a b a" is not found in the stream.

Example 3:

Stream: a a a a a a a
Pattern: a a a
Output: true

Constraints:

The pattern string's length will be between 1 and 10⁵.
The characters in the stream and pattern string are lowercase English letters.
You can only store a limited number of characters from the stream, ideally proportional to the length of the pattern.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What data types will the stream contain, and what is the nature of the data being streamed (e.g., strings, integers, objects)?
How is the 'infinite' stream represented or accessed (e.g., a generator, a function that returns the next element, a file)?
What defines a 'pattern'? Can you provide a more concrete example of the pattern we are searching for and how it's represented?
If the pattern is not found in the stream, what should the function return?
Are there any constraints on the size or complexity of the pattern to search for?

Brute Force Solution

Approach

The brute force method is like comparing the pattern against every single possible segment of the infinite stream. We painstakingly check each potential match, one after another. It's an exhaustive, but simple, way to find the pattern.

Here's how the algorithm would work step-by-step:

Start by assuming the pattern begins at the very beginning of the stream.
Check if the pattern matches the stream at that starting point.
If it doesn't match, shift the starting point of the pattern by one position further into the stream.
Repeat the matching process for this new starting position.
Continue shifting the starting point and checking for a match, one position at a time, across the entire stream (or until you find a match).
If a complete match is found, you've located the pattern.
If you exhaust the portion of the stream you're examining without finding a match, then the pattern does not exist in that section.

Code Implementation

def find_pattern_brute_force(stream, pattern):
    stream_length = len(stream)
    pattern_length = len(pattern)

    for stream_index in range(stream_length - pattern_length + 1):
        # Check if the pattern matches the stream at this starting index

        pattern_matched = True

        for pattern_index in range(pattern_length):
            if stream[stream_index + pattern_index] != pattern[pattern_index]:
                pattern_matched = False
                break

        # If a complete match is found, return True
        if pattern_matched:
            return True

    # If the entire stream is exhausted without finding a match
    # then the pattern does not exist in the stream
    return False

Big(O) Analysis

Time Complexity

O(n*m) – Let n be the length of the stream examined and m be the length of the pattern. The brute force approach iterates through the stream of length n, considering each position as a potential starting point for the pattern. For each of these n starting positions, it compares the pattern of length m to the corresponding segment of the stream. Therefore, in the worst case where a match is found only at the very end or not at all, the algorithm performs approximately n * m comparisons. Hence, the time complexity is O(n*m).

Space Complexity

O(1) – The brute force method described only involves shifting the starting point and comparing the pattern against the stream. No extra data structures like arrays, hash maps, or significant variables are created to store intermediate results or track visited positions. The algorithm uses a fixed amount of extra space, irrespective of the size of the stream or the pattern's length. Therefore, the auxiliary space complexity is constant.

Optimal Solution

Approach

The best way to find a pattern in a never-ending stream is to remember only what's necessary. We'll keep track of the pattern we are searching for and, as we look at each new piece of the stream, we will update our understanding of how much of the pattern we've seen so far.

Here's how the algorithm would work step-by-step:

First, let's create a way to remember the pattern we want to find and how much of it we've seen.
For each new piece of information that comes in, check if it matches the next part of the pattern we're looking for.
If it matches, then we remember that we've seen a little more of the pattern.
If it doesn't match, this new piece might be the start of the pattern all over again, so we check if it's the same as the beginning of our pattern.
If the current piece of stream is not a match, and it's also not the beginning of the pattern, then we reset our progress to zero, meaning we haven't seen any of the pattern yet.
If we ever see the entire pattern, we report that we've found it.
Repeat this process for every piece of information that comes in from the stream, without ever having to look back at previous data.

Code Implementation

def find_pattern_in_stream(stream, pattern):
    pattern_length = len(pattern)
    chars_matched = 0

    for stream_char in stream:
        # Check if current stream char matches the next pattern char
        if stream_char == pattern[chars_matched]:
            chars_matched += 1

            # Entire pattern found, reset for further matches
            if chars_matched == pattern_length:
                return True
        else:
            # Check if stream char matches the beginning of pattern
            if stream_char == pattern[0]:
                chars_matched = 1

            # Reset match if stream char doesn't start pattern
            else:
                chars_matched = 0

    return False

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input stream once, processing each element. For each element, it performs a constant amount of work: comparing it to the next character in the pattern, or resetting the pattern match progress. The length of the pattern is fixed and does not grow with the stream's size. Therefore, the time complexity is directly proportional to the number of elements in the input stream, denoted as n, resulting in O(n) time complexity.

Space Complexity

O(1) – The algorithm only needs to remember the pattern we are searching for (let's say its length is M, which is constant and independent of the stream size N) and how much of the pattern we have seen so far, which can be stored in a single integer variable. It does not use any auxiliary data structures that grow with the size of the input stream N. Therefore, the space complexity is constant.

Edge Cases

Case	How to Handle
Null input stream	Throw an IllegalArgumentException or return an empty list, depending on requirements.
Empty input stream	Return an empty list, as no pattern can be found in an empty stream.
Pattern is larger than the initially available stream data	Buffer enough data to accommodate the full pattern length before processing.
Very long stream with frequent, but slightly altered, near-matches to the pattern	Ensure efficient pattern matching algorithm to avoid quadratic time complexity in near match cases.
Pattern contains special characters or delimiters relevant to stream reading	Escape or handle these characters appropriately during stream processing and pattern matching.
Pattern occurs at the very beginning of the infinite stream	The matching algorithm should be able to find the pattern starting from the stream's first element.
Pattern never occurs in the infinite stream	Implement a mechanism to terminate the search after a reasonable time or data limit is reached and return an appropriate result (e.g., null or empty list).
Stream reading errors	Implement error handling to catch and log any exceptions that might occur while reading from the stream.

Null input stream

How to Handle:

Throw an IllegalArgumentException or return an empty list, depending on requirements.

Empty input stream

How to Handle:

Return an empty list, as no pattern can be found in an empty stream.

Pattern is larger than the initially available stream data

How to Handle:

Buffer enough data to accommodate the full pattern length before processing.

Very long stream with frequent, but slightly altered, near-matches to the pattern

How to Handle:

Ensure efficient pattern matching algorithm to avoid quadratic time complexity in near match cases.

Pattern contains special characters or delimiters relevant to stream reading

How to Handle:

Escape or handle these characters appropriately during stream processing and pattern matching.

Pattern occurs at the very beginning of the infinite stream

How to Handle:

The matching algorithm should be able to find the pattern starting from the stream's first element.

Pattern never occurs in the infinite stream

How to Handle:

Implement a mechanism to terminate the search after a reasonable time or data limit is reached and return an appropriate result (e.g., null or empty list).

Stream reading errors

How to Handle:

Implement error handling to catch and log any exceptions that might occur while reading from the stream.