Variable-Size Sliding Window Algorithm and example

Exploring the Sliding Window Algorithm in JavaScript: PART 2 — Variable-Size Window

In Part 1 of our blog series on the Sliding Window Algorithm, we explored fixed-sized windows and their applications. Now, in Part 2, we delve into variable-sized sliding windows by solving a common problem: finding the longest subarray with a sum less than or equal to a given value. We’ll provide a JavaScript algorithm, code implementation, and step-by-step explanation.

Variable-Size Window:

A variable-size window adjusts its size dynamically as it slides through the data. The window size may change based on specific conditions or rules set by the problem. Here’s how it works:

• Example: Suppose you’re tasked with finding the longest subarray with a sum less than or equal to a given value.

Practical Example: Finding the longest subarray with a sum less than or equal to a given value

Given an array of positive integers and a target sum k, find the length of the longest subarray (continuous subsequence) whose sum is less than or equal to k.

Here’s a visualization of the algorithm for the provided example array

Array:    [2, 1, 3, 4, 1, 2, 1, 5, 3]
Target k: 7

Step 1:
  left = 0
  right = 0
  currentSum = 2
  maxLength = 0
Step 2 (right = 1):
  currentSum = 3
  maxLength = 1 (right - left + 1)
Step 2 (right = 2):
  currentSum = 6
  maxLength = 2
Step 2 (right = 3):
  currentSum = 10 (exceeds k)
  currentSum -= nums[left] (2), left++
  currentSum = 8
  maxLength = 3
... (continue iteration)
Result: 4 (Maximum subarray length with sum <= k)

Code Implementation in JavaScript

function longestSubarraySum(nums, k) {
  let left = 0;
  let right = 0;
  let currentSum = 0;
  let maxLength = 0;

  while (right < nums.length) {
    currentSum += nums[right];
    
    while (currentSum > k) {
      currentSum -= nums[left];
      left++;
    }
    
    maxLength = Math.max(maxLength, right - left + 1);
    right++;
  }

  return maxLength;
}

const nums = [2, 1, 3, 4, 1, 2, 1, 5, 3];
const k = 7;
const result = longestSubarraySum(nums, k);
console.log("Longest Subarray Length:", result); // Output: 4

Step-by-Step Solution:

1. Initialize Pointers and Variables:

• Initialize two pointers, left and right, both starting at the first element.
• Initialize a variable currentSum to keep track of the current sum of elements within the window.
• Initialize a variable maxLength to store the length of the longest subarray found so far.

let left = 0;
let right = 0;
let currentSum = 0;
let maxLength = 0;

2. Iterate through the Array:

• Start iterating through the array while the right pointer is less than the array's length.
• In each iteration, add the element at the right pointer to currentSum.
• Check if currentSum exceeds the target sum k.
• If it does, move the left pointer to the right and subtract the element at the previous left position from currentSum. Repeat this process until currentSum is less than or equal to k.
• Update maxLength as the maximum of its current value and the difference between right and left (length of the current subarray).

while (right < nums.length) {
  currentSum += nums[right];
  
  while (currentSum > k) {
    currentSum -= nums[left];
    left++;
  }
  
  maxLength = Math.max(maxLength, right - left + 1);
  right++;
}

3. Return the Result:

• After the loop, maxLength will contain the length of the longest subarray with a sum less than or equal to k.

return maxLength; // Result: 4 (for subarray [1, 3, 4, 1])

This example illustrates how the variable-sized sliding window technique efficiently solves the problem of finding the longest subarray with a sum less than or equal to a given value, showcasing the flexibility and effectiveness of the Sliding Window Algorithm in action.

Choosing the Right Approach:

• Use Fixed-Size Window When: The problem explicitly specifies a fixed window size or length. The pattern or condition you are searching for has a constant size. Simplicity and predictability are priorities.
• Use Variable-Size Window When: The problem involves variable constraints or patterns. You need to optimize for an optimal solution within changing conditions. Flexibility and adaptability are required to meet problem-specific criteria.

Conclusion:

Throughout this journey, we’ve witnessed the power and adaptability of the sliding window technique. It allowed us to efficiently tackle a problem that required dynamically adjusting the window’s size based on specific conditions. By skillfully manipulating pointers and variables, we uncovered the length of the longest subarray that met our criteria, all while maintaining an elegant and concise code structure.

The Sliding Window Algorithm, whether in its fixed-size or variable-size form, is a versatile tool in the arsenal of algorithm designers and problem solvers. It equips us to navigate through data efficiently, making it suitable for an array of real-world challenges. By mastering this technique, you’ll be better prepared to tackle complex problems and optimize your algorithms for enhanced performance.

As we conclude Part 2, we encourage you to practice and apply the knowledge gained here to various problem-solving scenarios. Keep exploring, experimenting, and sharpening your algorithmic skills, and you’ll find that the Sliding Window Algorithm is a valuable companion on your journey through the world of computer science and programming.