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.

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.

03. Simplified Implementation

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

def calculateSubArraySums(nums, subArraySize):
    currentSum = 0
    result = []

    for i in range(len(nums)):
        currentSum += nums[i]  # Add the current element to the window sum

        if i >= (subArraySize - 1):  # Once the window size is reached
            result.append(currentSum)  # Store the sum
            currentSum -= nums[i - subArraySize + 1]  # Remove the first element of the window

    return result

# Example Usage
nums = [1, 2, 1, 2, 6, 7, 5, 1]
k = 2
result = calculateSubArraySums(nums, k)
print(result)

Explanation of the Code:

1. Initialization: currentSum keeps track of the sum of the current window, and 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:

def calculateSubArraySums(nums, subArraySize):
    currentSum = 0
    result = []
    i = 0  # Start pointer

    for j in range(len(nums)):  # 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.append(currentSum)  # Store the sum
            currentSum -= nums[i]  # Remove the first element of the window
            i += 1  # Slide the start pointer forward

    return result

# Example Usage
nums = [1, 2, 1, 2, 6, 7, 5, 1]
k = 2
result = calculateSubArraySums(nums, k)
print(result)

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.