Sliding Window Flashcards
(19 cards)
What is the sliding window pattern?
A technique for efficiently processing sequential data by maintaining a dynamic window that slides across the data.
How does the sliding window pattern work?
It involves counting elements in a fixed portion of the data and adjusting the window’s boundaries to track relevant elements.
What types of problems can the sliding window pattern solve?
Problems involving contiguous subarrays or substrings, such as finding maximum sums or detecting repeated patterns.
What is a fixed-size window?
A window where the size is constant, used for problems like finding the largest sum of any three consecutive numbers.
What is a dynamic window?
A window where the size changes based on conditions, such as finding the smallest subarray whose sum exceeds a target.
How are pointers used in the sliding window technique?
Two pointers represent the window’s boundaries and move through the data to examine a portion at a time.
In a fixed-size window, how do the pointers move?
Both pointers move together, keeping the window size constant.
In a dynamic window, how do the pointers operate?
One pointer expands the window while the other contracts it based on a condition.
How does the sliding window technique reduce time complexity?
It avoids nested loops and reuses previous calculations, reducing complexity to linear time O(n).
What is an example of a problem that can be solved using the sliding window pattern?
Finding the maximum sum subarray of size K.
What is another example of a sliding window problem?
Finding the length of the longest substring without repeating characters.
What conditions must be met for a problem to match the sliding window pattern?
- Contiguous data
- Processing subsets of elements
- Efficient computation time complexity
In telecommunications, how can the sliding window pattern be applied?
To find the maximum number of users connected to a cellular network’s base station in every k-millisecond interval.
How can the sliding window pattern be used in video streaming?
To calculate the median number of buffering events in each one-minute interval.
In social media content mining, what can the sliding window pattern help find?
The shortest sequence of posts by one user that includes all topics posted by another user.
True or False: The sliding window pattern can only be used for fixed-size windows.
False
Fill in the blank: The sliding window technique allows processing data in _______ time.
linear
Solution: Repeated DNA Sequences
Statement
A DNA sequence consists of nucleotides represented by the letters ‘A’, ‘C’, ‘G’, and ‘T’ only. For example, “ACGAATTCCG” is a valid DNA sequence.
Given a string, s, that represents a DNA sequence, return all the 10-letter-long sequences (continuous substrings of exactly 10 characters) that appear more than once in s. You can return the output in any order.
Solution summary
Let’s get a quick recap of the optimized solution:
Encode DNA sequence in s by converting ‘A’, ‘C’, ‘G’, and ‘T’ into numbers (0, 1, 2, 3) for easier computation.
Use a set to store seen hashes and detect repeating sequences.
Compute the rolling hash for the first 10-letter substring and store it in the set.
Move the window one step forward and compute the hash of the new window. Store this new hash in the set. Store the corresponding substring in the result if the calculated hash appears again.
Once the entire string has been traversed, return the result containing all the repeating 10-letter long sequences.
time complexity
Converting characters to numbers: O(n)
Computing the initial rolling hash: O(k) (treated as O(1))
Sliding through the string and updating the hash: O(n-k) (simplified to O(n))
Checking and storing hashes: O(1)
The overall time complexity is summarized as O(n) + O(1) + O(n) + O(1) = O(n).
space complexity
Storing the encoded sequence: O(n)
Storing hashes: O(n-k+1) (simplified to O(n))
Storing repeated sequences: O(n-k+1) (simplified to O(n))
The overall space complexity is summarized as O(n) + O(n) + O(n) = O(n).)
Python
def findRepeatedDnaSequences(s):
# Convert DNA string to numbers
to_int = {"A": 0, "C": 1, "G": 2, "T": 3}
encoded_sequence = [to_int[c] for c in s]
k = 10
n = len(s)
# If the string is shorter than 10 characters, return an empty list
if n <= k:
return []
a = 4 # Base-4 encoding
h = 0 # Hash value
seen_hashes, output = set(), set() # Sets to track hashes and repeated sequences
a_k = 1 # Stores a^L for efficient rolling hash updates
# Compute the initial hash for the first 10-letter substring
for i in range(k):
h = h * a + encoded_sequence[i]
a_k *= a
seen_hashes.add(h) # Store the initial hash
# Sliding window approach to update the hash efficiently
for start in range(1, n - k + 1):
# Remove the leftmost character and add the new rightmost character
h = h * a - encoded_sequence[start - 1] * a_k + encoded_sequence[start + k - 1]
# If this hash has been seen_hashes before, add the corresponding substring to the output
if h in seen_hashes:
output.add(s[start:start + k])
else:
seen_hashes.add(h)
return list(output) # Convert set to list before returning
Statement
Given an integer list, nums, find the maximum values in all the contiguous subarrays (windows) of size w.
Solution Summary
Solution Summary
To recap, the solution can be divided into the following parts.
First, we check if the input list contains only one element.
If it does, we directly return the input list because there is only one maximum element.
Then, we process the first ‘w’ elements of the input list.
We will use a deque to store the indexes of the candidate maximums of each window.
For each element, we perform the clean-up step, removing the indexes of the elements from the deque whose values are smaller than or equal to the value of the element we are about to add to the deque.
Then, we append the index of the new element to the back of the deque.
After the first ‘w’ elements have been processed, we append the element whose index is present at the front of the deque to the output list as it is the maximum in the first window.
After finding the maximum in the first window, we iterate over the remaining input list.
For each element, we repeat Step 3 as we did for the first ‘w’ elements.
Additionally, in each iteration, before appending the index of the current element to the deque, we check if the first index in the deque has fallen out of the current window.
If so, we remove it from the deque.
Finally, we return the list containing the maximum elements of each window.
Time complexity
The input parameters of the function are a list of integers, and an integer specifying the size of the window. In the discussion that follows, we will use n
to represent the size of the list of integers, and w
to represent the size of the window.
To get a clearer understanding of the time complexity of our solution, we need to consider the different ways in which the values in the input list change. The values in the list can be:
Strictly increasing
Strictly decreasing
Constant
Mixed, for example, increasing, decreasing, constant, then decreasing again, then constant, then increasing, then constant and then decreasing
Hence, the time complexity of the solution, considering the worst of these four cases, is
O
(
n
)
O(n)
.
Space complexity
The space complexity of this solution is
O
(
w
)
O(w)
, where
w
w
is the window size.
