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

1. 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:

1. 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.

2. 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.

3. 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:

1. 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.
2. 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.
3. 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.
4. When the sum of the current window becomes less than the target number, we can again enlarge the window from the right side.
5. 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.