Skip to main content

Calculating Subarray Sums Using Two Pointers Using Javascript

Calculating Subarray Sums Using Two Pointers

Efficient computation of subarray sums is a common problem in programming. One effective approach is the two-pointer technique, which allows for efficient sliding-window operations. Below, we explain the implementation of such a method step by step, with a focus on JavaScript.


01. Problem Statement

Given an array of integers nums and a positive integer subArraySize, compute the sum of all subarrays of size subArraySize. The goal is to achieve this efficiently using the two-pointer technique.


02. Understanding the Two-Pointer Technique

The two-pointer technique involves using two indices to represent a sliding window over the array. As the window moves:

  • The end pointer adds new elements to the window.
  • The start pointer removes elements that are no longer part of the window.

This approach minimizes unnecessary recalculations, maintaining a running sum as the window slides. The technique is both intuitive and efficient for problems requiring operations on contiguous segments of an array.


03. Simplified Implementation

Here is a simplified implementation of the subarray sum calculation using the two-pointer technique in JavaScript:

function calculateSubArraySums(nums, subArraySize) {
  let currentSum = 0;
  const result = [];

  for (let i = 0; i < nums.length; i++) {
    currentSum += nums[i]; // Add the current element to the window sum

    if (i >= subArraySize - 1) { // Once the window size is reached
      result.push(currentSum); // Store the sum
      currentSum -= nums[i - subArraySize + 1]; // Remove the first element of the window
    }
  }

  return result;
}

// Example Usage
const nums = [1, 2, 1, 2, 6, 7, 5, 1];
const k = 2;
const result = calculateSubArraySums(nums, k);
console.log(result); // Output: [3, 3, 3, 8, 13, 12, 6]

Explanation of the Code:

  1. Initialization: The variable currentSum keeps track of the sum of the current window, and the array result stores the sums of all subarrays.
  2. Window Expansion: Each element is added to currentSum as the loop progresses.
  3. Window Size Check: When the window reaches the required size (subArraySize), the sum is appended to result.
  4. Sliding the Window: The first element of the window (nums[i - subArraySize + 1]) is subtracted as the window slides forward.

Output:

For nums = [1, 2, 1, 2, 6, 7, 5, 1] and k = 2, the output is:

[3, 3, 3, 8, 13, 12, 6]

04. Combining with Two-Pointer Approach

We can refine the logic while explicitly maintaining two pointers (i and j) to make the two-pointer mechanism more intuitive:

function calculateSubArraySumsWithPointers(nums, subArraySize) {
  let currentSum = 0;
  const result = [];
  let i = 0; // Start pointer

  for (let j = 0; j < nums.length; j++) { // End pointer
    currentSum += nums[j]; // Add current element to the window sum

    if (j - i + 1 === subArraySize) { // When the window reaches the required size
      result.push(currentSum); // Store the sum
      currentSum -= nums[i]; // Remove the first element of the window
      i++; // Slide the start pointer forward
    }
  }

  return result;
}

// Example Usage
const resultWithPointers = calculateSubArraySumsWithPointers(nums, k);
console.log(resultWithPointers); // Output: [3, 3, 3, 8, 13, 12, 6]

Key Differences in This Approach:

  • Explicit Two Pointers: i and j are explicitly defined for clarity.
  • Sliding the Window: The start pointer i moves forward when the window size is met.

Output:

The output remains the same:

[3, 3, 3, 8, 13, 12, 6]

05. Time and Space Complexity

Time Complexity:

  • Both implementations iterate through the array once, with each element added and removed from the currentSum exactly once.
  • Overall Time Complexity: $O(n)$, where $n$ is the length of the array.

Space Complexity:

  • Only a few variables are used to store intermediate results and the result list.
  • Overall Space Complexity: $O(k)$, where $k$ is the size of the result list.

06. Conclusion

Both implementations efficiently compute subarray sums using the two-pointer technique. The refined approach with explicit pointers provides better clarity, while the simplified implementation is more compact. Choose the one that best suits your coding style and readability preferences. JavaScript's simplicity and flexibility make it an excellent choice for such problems, demonstrating the power of fundamental algorithms.

Comments