Technical Interviews: Everything You Need to Master the Sliding Window Technique
Every sliding window problem (arrays) follows one of these patterns…
Securing a spot in a coding interview is no small feat. It’s a competitive market in technology, and being well-prepared is key.
But it’s not just about finding solutions. What sets the best candidates apart is their ability to clearly communicate their thought process and the strategic-thinking they show.
This means interviewers only really pay attention to how you navigate through a problem, not whether you solve it. That’s what makes or breaks the success of your coding interview.
The best way to prepare is by practising a lot and learning how to recognise patterns in questions and use the right techniques to solve them.
For this reason, I’ve created a “roadmap” of articles to walk us through every type of question we might encounter and the most efficient ways to tackle them, starting with the Sliding Window Technique used in arrays.
The Sliding Window Technique
The Sliding Window technique involves defining a window or range in the input data and then moving that window across the data to perform some operation within the window.
What’s its Advantage?
- Optimises solutions from O(n²) time complexity (naïve brute force approach) to O(n) time complexity.
- Prevents unnecessary iterations and duplicated work.
How Can You Recognise it?
- Max/Min of Subarrays: Find the maximum/minimum x (sum, product, etc) of any subarray.
- Longest/Shortest Subarray: Find the longest/shortest subarray satisfying condition x.
- Count/Find Elements in Subarray: Count/find elements in each subarray satisfying condition x.
Solved Examples in Python — Fixed Size
Q1. Find the maximum sum of a contiguous subarray of size k = 3 within the array arr[] = [4, 1, 2, 6, 8, 3, 1, 5].
def getMaxSum(arr, k):
# Add your code hereIf you’re new to the technique, start by visualising the fixed-size sliding window used in this example.
The key is to identify which element to remove and which to add at each step. This is what “slides” the window.
Compare your implementation with the solution below; comments have been added to explain each step.
def getMaxSum(arr, k):
"""
Calculates the maximum sum of any subarray of size
'k'.
Parameters:
arr (array): The array from which subarrays are
to be considered.
k (int): The size of the subarray for which the
maximum sum is to be calculated.
Returns:
int: The maximum sum of any subarray of size 'k'.
"""
n = len(arr)
# n must be greater than k
if n <= k:
print("Invalid")
return -1
# Initialise maximum sum
max_sum = sum(arr[:k])
# Compute the sums of remaining windows
for i in range(n - k):
window_sum = window_sum - arr[i] + arr[i + k]
max_sum = max(window_sum, max_sum)
return max_sumQ2. Given an array arr[] = [1, 3, 2, 4, 3, 2, 2, 2] and an integer k = 4, print the count of distinct numbers in all subarrays of size 4.
def printDistinctSubCounts(arr, k):
# Add your code here
You need an additional data type — a dictionary — to keep track of the count of elements in the current window of size k = 4.
def printDistinctSubCounts(arr, k):
"""
Prints the count of distinct elements in all subarrays
of size 'k'.
Parameters:
arr (array): The array in which subarrays are to be
considered.
k (int): The size of each subarray for which the
distinct element count is calculated.
Returns:
None: This function does not return anything.
"""
n = len(arr)
d = {}
dist_count = 0
# Iterate through first window
for i in range(k):
# Initialise distinct counts
d[arr[i]] = d.get(arr[i], 0) + 1
if d[arr[i]] == 1:
dist_count += 1
print(dist_count)
# Iterate through remaining windows
for i in range(k, n):
# Remove the first element of the previous window
# If there was only one occurrence, reduce count
if d[arr[i - k]] == 1:
dist_count -= 1
d[arr[i - k]] -= 1
# Add the new element of the current window
# If it appears for the first time, increase count
d[arr[i]] = d.get(arr[i], 0) + 1
if d[arr[i]] == 1:
dist_count += 1
# Print count of the current window
print(dist_count)Variable Size
Q3. Find the size of the shortest subarray containing at least one element with a sum greater than the k = 5 within the array arr[] = [3, 1, 2, 6, 8, 3].
def getMinSubSize(arr, k):
# Add your code hereAgain, start by visualising the variable-size sliding window and steps. Do you see a pattern?
The key to these questions is to use ‘start’ and ‘end’ pointers for each subarray and know when to update them.
def getMinSubSize(arr, k):
"""
Finds the minimum size of a subarray whose
sum is greater than 'k'.
Parameters:
arr (array): The array from which subarrays are
to be considered.
k (int): The threshold sum that the subarray
needs to exceed.
Returns:
int: The minimum size of a subarray with a sum
greater than 'k'. If no such subarray exists,
returns -1.
"""
n = len(arr)
start = 0
cur_sum = 0
# Initialise minimum size of subarray
min_size = -1
for end in range(n):
cur_sum += arr[end]
while cur_sum > k:
# Move the start pointer to the right
cur_sum -= arr[start]
start += 1
# Update min_size
min_size = min(min_size, end - start + 1)
return min_sizeQ4. Given an array arr[] = [1, 5, 3, 7, 2, 8, 4, 12, 9, 2, 6] and an integer sum = 24, find the shortest subarray containing at least one element that adds to the target sum.
I’ve deliberately used a different loop structure — a while loop — below to emphasise the importance of not memorising one solution and being adaptable when you tackle these types of questions.
Focus on the underlying patterns, not the surface-level questions.
def getMinSubSum(arr, x):
"""
Finds the subarray with the smallest length
that has a sum at least as large as 'x'.
Parameters:
arr (array): The array to search within.
x (int): The target sum the subarray should reach
or exceed.
Returns:
array: The subarray with the smallest length
that meets or exceeds the sum 'x'. If no such
subarray exists, returns an empty array.
"""
start, end = 0, 0
n, min_len = len(arr), len(arr)+1
cur_sum, targ_sum = arr[0], x
result = []
# Check if the sum of the entire array is less
# than the target sum
if sum(arr) < targ_sum:
return result
# Check if the target sum is an element of the
# array
elif targ_sum in arr:
return [targ_sum]
# Iterate over the entire array
while end < n:
if cur_sum >= targ_sum:
window = arr[start:end + 1]
# If current sum is equal to the target sum,
# update the minimum length and result
if (cur_sum == targ_sum) and (len(window) < min_len):
min_len = len(window)
result = window
# Move the start pointer to the right,
# shrinking the window
cur_sum -= arr[start]
start += 1
else:
# Move the end pointer to the right,
# growing the window
end += 1
if end < n:
cur_sum += arr[end]
return resultIt’s your turn now! Test your understanding and share your answers to the next two questions in the comments below.
Learning comes from practice and application, not observation.
Q5. Given a string str, find the length of the longest substring without repeating characters
Q6. Given two strings — str and pat— find the smallest substring in str containing all characters of pat.
Thanks for reading this! Share your thoughts in the comments and clap if you enjoyed it. It helps me a lot.
