Algorithm Series: Guide to the Sliding Window Technique

The sliding window technique is a popular algorithmic approach used to efficiently solve problems that involve finding a subset, subarray, or substring that meets certain conditions. It involves creating a “window” that slides through the data structure while keeping track of relevant information. The sliding window technique is particularly useful when dealing with arrays or strings. In this article, we will explore the concept of the sliding window technique and provide detailed examples implemented in JavaScript.

Understanding the Sliding Window Technique

The sliding window technique involves maintaining a window of elements within a given data structure, such as an array or a string. This window starts at one end and moves through the data structure in a predefined manner. As the window slides, we update the window’s contents and track any relevant information or conditions. By efficiently updating and maintaining the window, we can optimize the time complexity of our algorithm.

Example 1: Maximum Sum Subarray

Let’s consider the Maximum Sum Subarray problem as an example to demonstrate the sliding window technique. Given an array of integers, we need to find the contiguous subarray with the maximum sum. Here’s a step-by-step implementation using the sliding window technique:

function maxSubarraySum(nums, k) {
  let maxSum = 0;
  let windowSum = 0;
  let windowStart = 0;

  for (let windowEnd = 0; windowEnd < nums.length; windowEnd++) {
    windowSum += nums[windowEnd];

    if (windowEnd >= k - 1) {
      maxSum = Math.max(maxSum, windowSum);
      windowSum -= nums[windowStart];
      windowStart++;
    }
  }

  return maxSum;
}

const nums = [2, 1, 5, 1, 3, 2];
const k = 3;
console.log(maxSubarraySum(nums, k)); // Output: 9

In this example, we use two pointers, windowStart and windowEnd, to define our sliding window. We initialize maxSum as 0 to track the maximum sum found so far. We also maintain a windowSum variable to keep track of the current sum of elements within the window.

We start by moving the windowEnd pointer to the right, adding the value of nums[windowEnd] to the windowSum. We only begin updating the maximum sum when the window size reaches k (i.e., windowEnd is greater than or equal to k - 1).

Once the window size reaches k, we compare the current windowSum with the maxSum and update maxSum if necessary. Then, we subtract the value of nums[windowStart] from windowSum and move the windowStart pointer to the right.

We continue this process, expanding and shrinking the window, until we have considered all possible subarrays of size k. Finally, we return the maxSum, which represents the maximum sum of any contiguous subarray of size k.

Example 2: Longest Substring Without Repeating Characters

Another application of the sliding window technique is finding the longest substring without repeating characters in a given string. Here’s an implementation using the sliding window technique:

function longestSubstring(str) {
  let maxLength = 0;
  let start = 0;
  let charMap = {};

  for (let end = 0; end < str.length; end++) {
    const currentChar = str[end];

    if (charMap[currentChar] !== undefined && charMap[currentChar] >= start) {
      start = charMap[currentChar] + 1;
    }

    charMap[currentChar] = end;
    maxLength = Math.max(maxLength, end - start + 1);
  }

  return maxLength;
}

const str = "abcabcbb";
console.log(longestSubstring(str)); // Output: 3

In this example, we use the start and end pointers to define our sliding window. We also maintain a charMap object to store the indices of characters encountered so far. As we iterate through the string, we check if the current character has been seen before within the current window. If it has, we update the start pointer to the next index after the last occurrence of that character. We update the charMap with the current character’s index and calculate the length of the current window. The maximum length encountered is stored in the maxLength variable.

Conclusion

The sliding window technique is a powerful algorithmic approach for solving problems involving subsets, subarrays, or substrings. It provides an efficient way to process data sequentially and optimize the time complexity of our solutions. In this article, we explored the concept of the sliding window technique and provided detailed examples using JavaScript. By mastering this technique, you can effectively tackle a wide range of programming challenges and enhance your problem-solving skills.

Remember to practice implementing the sliding window technique in different problem scenarios to further solidify your understanding. Happy coding!