If you’re having a coding interview, and that you are overwhelmed by the number of coding problems out there, you’re not alone. Especially when you are in a hurry, you want to grasp as much problem solving skills as possible, and this article ( and other parts coming up ) exist to help you with that.
When tackling a coding problem, there is generally a pattern of how to solve it; what I mean by pattern is the way you want to approach the problem efficiently ( in terms of space and time complexity ) based on the problem requirements.
Problem
Let’s look at a specific problem to showcase today’s pattern in practice.
The first simple solution that may come to mind is to compute the average of all possible sub-arrays and return the maximum value.
class Solution:
def findMaxAverage(self, nums: List[int], k: int) -> float:
max_avg = -1000
for i in range(len(nums) - k + 1):
current_sum = 0
for j in range(i, i + k):
current_sum += nums[j]
max_avg = max(max_avg, current_sum / k)
return max_avg
This solution works fine, however we may encounter some potential problems with it :
- Time complexity : O(n*k) : So for example, If $n = 100,000$ and $k = 50,000$, this solution would perform roughly 5 billion operations
- Time Limit Exceeded issue: For large inputs, and in specific environment settings, this solution may resolve in a time limit issue because the environment has a threshold of operations per second. For example, in LeetCode, for a large input it has raised the TLE error.
- Outside online problem solving platforms, in a real-world solution, this may result in high CPU usage which may result in potential “hangs” for the users
Optimization through the Sliding Window Pattern
We could improve the solution using a sliding window pattern :
As the name suggests, we try to construct a window that grows and shrinks according to the requirements of the problem, and perform the main solution within that window. Let me showcase that:
class Solution:
def findMaxAverage(self, nums: List[int], k: int) -> float:
current_sum = 0
left = 0 # Left boundary of the window
avg = 0
max_avg = -1000
# The index used inside the loop represents the right boundary of the window
# So window size is: right - left + 1
for right in range(len(nums)):
diff = right - left + 1
current_sum += nums[right]
# If window's size attains the required length for the subset
# we have to adjust its size by incremeting the left index
# after calculating the average value
if diff == k:
avg = current_sum / k
max_avg = max(avg,max_avg)
current_sum -= nums[left]
left +=1
return max_avg
This algorithm optimizes the previous solution with O(n) time complexity and the same O(1) space complexity.
When to use this pattern
When dealing with linear data structures ( lists, string,… )
The solution has to deal with finding some subset
What’s next ? Practice
You may use the LeetCode platform online and pick some sliding window problems from there to practice. You have a set of 161 questions !
PS: Some of these problems may be solved efficiently, not only by using this pattern. Keep in mind that a pattern exists to help you with one way of solving a problem when some requirements are gathered, but may not be the only approach we could use !
See you in the next article for another coding pattern !
Top comments (0)