Last Journal: Beginner Problem Solving Pattern Part 4

Photo by XiaoLu Li on Unsplash

This article would be the last blog for beginner problem-solving pattern journals. You can check all the previous journals here: part1, part 2, part3. Lastly, in this article, I want to introduce you, a ‘sliding window’ problem-solving pattern.

What is a ‘Sliding Window’?

Sliding Window pattern involves creating a window that can either be an array or number from one position to another. Depending on a particular condition, the window either increases or closes (and a new window is created). Usually, we start the window from the left of the array/string, but you could also start from right to left or middle. However, we usually slide it up from left to right. The sliding window is handy for keeping track of a subset of data in a broader set of data array/string, etc.

Example:

Before we start solving the problem, we need to understand the problem first. The maxSubarraySum function accepts an array of integers and a number called n, finding the maximum sum of consecutive n in the array. The first example should result in 10 because [2,8] is the maximum subarray sum of 2 numbers in the array. The second example should return 17; since the sum of [2,5,2,8] is the maximum subarray sum of 4 numbers in the array, 17.

There are a couple of ways of solving the problem. This problem is a perfect example of utilizing the sliding window technique to solve the problem. But, first, let’s solve the problem with a naive approach.

Naive Solution

Naive Solution: Brute Force, Time Complexity O(N²)

The time complexity of this approach is O(N²), which is an inefficient solution if we assume having ten of thousands of data in the array. A better way of solving the problem more efficiently is to utilize the sliding window technique.

Better Solution

Better Solution: Sliding Windows, Time Complexity :O(N)

This approach’s time complexity is linear time O(N), which is much better than the previous method. Essentially what we are doing is at the very beginning, we sum together the first n consecutive indexes. We can do it linearly by adding the next index number and minus the most left side index number in that window rather than starting another loop for getting the sum. The following 4 pictures will show how the sliding window works in more detail.

Left: Start getting the sum of n consecutive first. In this case, n=3. Middle: add the next value, expanding the window. Right: remove the first index as we need to keep it as n(3) consecutive items only.

Repeat the same process until the end of the array index.

Conclusion

This article concludes Beginner Problem solving pattern journals. Knowing these common patterns helps your approach to problem-solving questions, but that doesn’t mean you will cover all the possible questions on earth. It might help you in 2 out of 5 questions in coding challenges yet better than 0 out of 5 questions in coding challenges. These are just the most common problem-solving patterns for beginners. There are still more advanced patterns such as recursive, dynamic programming, backtracking, greedy, prefix sum…etc. Lastly, suppose you want to get better at problem-solving skills and recognizing patterns fast. In that case, there are no direct short cuts; you need to keep practicing a lot of problems and understanding the institution behind each problem you solve. Like boxer Manny Pacquiao says, practice doesn’t make perfect; practice makes progress.

References:

JavaScript (JS) Algorithms and Data Structures Masterclass