A Beginner's Guide to the Sliding Window Algorithm with JavaScript
\
The sliding window is an algorithm typically used for strings or arrays, which allows analyzing a subset of data using a window of fixed or dynamic size. Simply put, the window, in this case, is a substring or subarray. This window can be moved forward across the data set, effectively analyzing changes within the window without having to recalculate it entirely each time. For instance, this algorithm can be used to find the subarray of minimal length whose sum of elements is greater or equal to a given number N or to find the longest substring without repeating characters.
\
The efficiency of the algorithm comes from the fact that each element is examined only once, thus achieving linear complexity O(n). This is a significant advantage over the brute force approach, which requires a nested loop and results in quadratic complexity O(n²).
\
Basic Steps of the Algorithm
Set the window boundaries by initializing left and right pointers. These pointers essentially serve as variables for the left and right indices of the window. For example, in the array [1,2,3,4], the left pointer at 1 and the right pointer at 2 point to the window [2,3]. Typically, the pointers are set at the initial position of the string/array.
\
2) Start shifting/expanding the window. Move the right pointer to consider more elements.
\
\
3) Check the conditions within the current window. As soon as the conditions are not met, move the left pointer until the given conditions are satisfied again.
\
4) Repeat steps 2 and 3 until the end is reached (when the right pointer hits the end of the array/string).
\
Practical Examples
Finding the Longest Substring Without Repeating Characters
The essence of the task is simple. Given a string s, it is necessary to find the longest substring that does not contain repeating characters. This task can simply be solved by brute force, using a nested loop to build all possible substring options and analyze them. However, this approach is highly inefficient with quadratic complexity, O(n²). The task can be solved more optimally using the sliding window. Here are the steps to follow:
Initialize the left and right pointers at position 0. Initialize an empty hash to store discovered characters, allowing us to quickly answer whether we have already seen a character and at what position. Also, initialize a variable to store the found substring.
While the right pointer has not reached the end of the string, check if the character at the right pointer exists in our hash.
2.1. If not, add the character to the hash and move the right pointer. Essentially, the hash records the character and the position it was found.
2.2. If it exists, compare whether the current substring between the left and right pointer is longer than the previously found substring. If yes, update the substring variable. Also, the current window can no longer be moved right; it needs to be narrowed from the left until the current character is unique in the hash. Since the position of the character(where it was found) is stored in the hash, the left pointer can be moved to the right of this character’s position. Thus, we once again have a window with unique characters inside.
Repeat step 2 until the right pointer reaches the end of the string.
\
const lengthOfLongestSubstring = function(s) {
let hash = {};
let left = 0;
let right = 0;
let maxSubStr = '';
while (right < s.length) {
const char = s[right];
if (char in hash && hash[char] >= left) {
left = hash[char] + 1;
}
hash[char] = right;
const curSubStr = s.slice(left, right + 1);
if (maxSubStr.length < curSubStr.length) {
maxSubStr = curSubStr;
}
right++;
}
return maxSubStr;
};
\
Finding the Minimum Size Subarray Sum
There is an array of numbers and a given number target. It is necessary to find the subarray of minimal length, the sum of whose elements is greater than or equal to the target. As in the previous example, this task could be solved using a nested loop, building all possible subarrays from each index. Consider how the sliding window allows solving this task more optimally:
Again, initialize the left and right pointers at index 0 of the array. Also, initialize a variable to store the sum of the elements in the current window as 0, and another variable to store the minimum length. This can be initialized inversely; since we need the minimal length, initialize it to Infinity.
While the right pointer has not reached the end of the array, increase the sum of the current window by the value of the element at the right pointer’s position.
While the sum of the current window is greater than or equal to the target number, try to narrow the window from the left side, simultaneously checking if the length of the current subarray is less than the already found minimum length.
When the sum of the current window becomes less than the target number, we can again enlarge the window from the right side.
Continue steps 2, 3, and 4 until we reach the end of the array.
\
const minSubArrayLen = function(target, nums) {
let left = 0;
let right = 0;
let minLen = Infinity;
let curSum = 0;
while (right < nums.length) {
curSum += nums[right];
while (curSum >= target) {
minLen = Math.min(minLen, right - left + 1);
curSum -= nums[left];
left++;
}
right++;
}
return isFinite(minLen) ? minLen : 0;
};
\
Conclusion
Thus, we have looked at what the sliding window method is and how it can be useful in solving various tasks. This algorithm is particularly effective when analyzing subsequent parts of data because its main advantage is the ability to ensure linear execution time through the efficient reuse of results from previous calculations. I hope this was interesting and clear, and you will be able to apply the full potential of this method to solve your tasks.
\
Welcome to Billionaire Club Co LLC, your gateway to a brand-new social media experience! Sign up today and dive into over 10,000 fresh daily articles and videos curated just for your enjoyment. Enjoy the ad free experience, unlimited content interactions, and get that coveted blue check verification—all for just $1 a month!
Account Frozen
Your account is frozen. You can still view content but cannot interact with it.
Please go to your settings to update your account status.
Open Profile Settings