Window Sum

Question (LC.604)

Given an array of n integers, return the window sum of window size k.

Example

I: [1,2,7,8,5], k = 3
O: [10,17,20]
1+2+7 = 10
2+7+8 = 17
7+8+5 = 20

Analysis

The brute force approach is just to slide the window and sum each window. The time complexity will be O(nk).

Code

public int[] winSum(int[] nums, int k) {
    int[] results = new int[0];
    if (nums == null || nums.length < k || k < 1) {
        return results;
    }

    results = new int[nums.length - k + 1];
    int sum = 0;
    int index = 0;
    for (int i = 0; i <= nums.length - k; i++) {
        sum = 0;
        for (int j = i; j < i + k; j++) {
            sum += nums[j];
        }
        results[index++] = sum;
    }
    return results;
}

Optimization

We see clearly we are doing repetitive work. 1+2+7 and 2+7+8 both share 2+7. We can do this in one go as long as we take out the first one then add the new element.

Optimized Code

public int[] winSum(int[] nums, int k) {
    int[] results = new int[0];
    if (nums == null || nums.length < k || k < 1) {
        return results;
    }
    results = new int[nums.length - k + 1];
    int sum = 0;
    int index = 0;
    // compute the first window
    for (int i = 0; i < k; i++) {
        sum += nums[i];
    }
    results[index++] = sum;
    // rolling sum
    for (int j = k; j < nums.length; j++) {
        sum -= nums[j - k];
        sum += nums[j];
        results[index++] = sum;
    }
    return results;
}