Maximum sum sub-array of size k

You're in a phone screen and the interviewer says, "Given an array of positive integers and a number k, find the maximum sum of any contiguous sub-array of size k." It sounds straightforward, and it is, but the follow-up question is where it gets interesting: "Can you do it in O(n) time, independent of k?" This is a classic introduction to the sliding window technique, also known as "Maximum Sum Subarray of Size K" on other platforms. It tests whether you can spot redundant computation and eliminate it.

TL;DR

Maintain a running sum of k consecutive elements. As you move through the array, add the new element entering the window and subtract the element leaving it. Track the maximum sum seen across all windows. This runs in O(n) time and O(1) space because each element is processed exactly once.

Prefer a different language? Jump to solutions in other languages.

Why This Problem Matters

The maximum sum sub-array of size k is the entry point for sliding window problems. If you understand this one, you have the core pattern for dozens of harder problems: longest substring without repeating characters, minimum window substring, and sliding window maximum, to name a few. Interviewers use it as a gauge for whether you can optimize beyond brute force.

Understanding the Problem

Given an array of n positive integers and an integer k, find the maximum sum of any contiguous sub-array of size k.

For the array [2, 1, 5, 1, 3] with k = 3, all possible windows of size 3 are:

Three windows, three sums: 8, 7, and 9. The maximum is 9, from the sub-array [5, 1, 3].

Constraints

• k is less than or equal to the array length
• 1 ≤ n ≤ 1000
• All elements are positive (≥ 1)
• 1 ≤ k ≤ 100

Edge Cases

1. k equals array length: The entire array is the only window
2. k equals 1: The answer is simply the maximum element
3. All elements identical: Every window has the same sum

The Brute Force Approach

The obvious solution is to check every window: for each starting index from 0 to n - k, sum up k elements and track the maximum. That gives O(n * k) time.

// Brute force: O(n * k)
int maxSum = 0;
for (int i = 0; i <= arr.length - k; i++) {
    int windowSum = 0;
    for (int j = i; j < i + k; j++) {
        windowSum += arr[j];
    }
    maxSum = Math.max(maxSum, windowSum);
}

The problem with this approach is the redundant work. When moving from window [2, 1, 5] to [1, 5, 1], we're recalculating the sum of the overlapping portion [1, 5]. The sliding window technique eliminates this overlap.

The Sliding Window Insight

When the window slides one position to the right, only two things change: one element leaves (the leftmost) and one element enters (the new rightmost). Instead of re-summing the entire window, update the sum incrementally:

newSum = oldSum - arr[left] + arr[right]

This single observation drops the time complexity from O(n * k) to O(n). Each element is added to the sum once and subtracted once.

Building the Algorithm

The approach uses a left pointer and a right pointer to define the window:

1. Expand the window by moving right forward, adding each element to windowSum
2. Once the window reaches size k, record maxSum if windowSum is larger
3. Shrink the window by subtracting arr[left] and incrementing left
4. Repeat until right reaches the end

Here is the full walkthrough. Use the controls to step through each iteration:

Notice how the window grows to size 3, then maintains that size by sliding one position at a time. The green highlight indicates windows that update maxSum.

Implementation

public class Solution {
  public int maxSum(int[] arr, int k) {
    int windowSum = 0, maxSum = 0;
    int left = 0;

    for (int right = 0; right < arr.length; right++) {
      // Expand: add the current element to the window
      windowSum += arr[right];

      // When the window reaches size k
      if (right - left + 1 == k) {
        // Update the maximum
        maxSum = Math.max(maxSum, windowSum);
        // Shrink: remove the leftmost element
        windowSum -= arr[left++];
      }
    }

    return maxSum;
  }
}

Walking through this with [2, 1, 5, 1, 3] and k = 3:

The final answer is 9.

Complexity Analysis

Time Complexity: O(n)

The right pointer visits each element exactly once, performing O(1) work per iteration (one addition, one comparison, and at most one subtraction). The total work is proportional to the array length, independent of k.

Space Complexity: O(1)

We use three variables (windowSum, maxSum, left) regardless of input size. No auxiliary data structures are needed.

Comparison with Brute Force

For an array of 10,000 elements with k = 100, the brute force does roughly 1,000,000 operations while the sliding window does 10,000.

Common Pitfalls

1. Off-by-one in window size check: The window has exactly k elements when right - left + 1 == k, not right - left == k. Forgetting the + 1 means you'll process windows of size k+1.

2. Sliding before recording: Make sure to update maxSum before subtracting arr[left]. If you shrink first, you lose the current window's sum.

3. Initializing maxSum to Integer.MIN_VALUE: Since all elements are positive, initializing to 0 works fine here. For problems with negative numbers, you would need Integer.MIN_VALUE.

4. Forgetting to increment left: The left++ is what keeps the window at exactly size k. Missing it causes the window to grow unbounded.

Interview Tips

When this problem comes up:

1. Start by describing the brute force O(n * k) approach, then explain why it's inefficient
2. Draw the array and physically show the window sliding, highlighting the overlap between consecutive windows
3. Mention that the same pattern generalizes to variable-width windows for harder problems
4. Test with k = 1 (should return the max element) and k = array length (should return the total sum)

If the interviewer asks follow-ups, common ones include:

• "What if k can vary?" (variable-width sliding window)
• "What if you need the maximum element in each window?" (sliding window maximum with a deque)
• "What if elements can be negative?" (Kadane's algorithm for arbitrary-length subarrays)

Solutions in Other Languages

Python

class Solution:
    def max_sum(self, arr, k):
        window_sum, max_sum = 0, 0
        left = 0

        for right in range(len(arr)):
            window_sum += arr[right]

            if right - left + 1 == k:
                max_sum = max(max_sum, window_sum)
                window_sum -= arr[left]
                left += 1

        return max_sum

JavaScript

class Solution {
  maxSum(arr, k) {
    let windowSum = 0, maxSum = 0;
    let left = 0;

    for (let right = 0; right < arr.length; right++) {
      windowSum += arr[right];

      if (right - left + 1 === k) {
        maxSum = Math.max(maxSum, windowSum);
        windowSum -= arr[left++];
      }
    }

    return maxSum;
  }
}

TypeScript

class Solution {
  maxSum(arr: number[], k: number): number {
    let windowSum = 0, maxSum = 0;
    let left = 0;

    for (let right = 0; right < arr.length; right++) {
      windowSum += arr[right];

      if (right - left + 1 === k) {
        maxSum = Math.max(maxSum, windowSum);
        windowSum -= arr[left++];
      }
    }

    return maxSum;
  }
}

C++

#include <iostream>
#include <algorithm>
#include <vector>

class Solution {
public:
  int maxSum(std::vector<int> arr, int k) {
    int windowSum = 0, maxSum = 0;
    int left = 0;

    for (int right = 0; right < arr.size(); right++) {
      windowSum += arr[right];

      if (right - left + 1 == k) {
        maxSum = std::max(maxSum, windowSum);
        windowSum -= arr[left++];
      }
    }

    return maxSum;
  }
};

Go

func (s *Solution) MaxSum(arr []int, k int) int {
    windowSum, maxSum := 0, 0
    left := 0

    for right, num := range arr {
        windowSum += num

        if right - left + 1 == k {
            if windowSum > maxSum {
                maxSum = windowSum
            }
            windowSum -= arr[left]
            left++
        }
    }

    return maxSum
}

Scala

class Solution {
  def maxSum(arr: Array[Int], k: Int): Int = {
    var windowSum = 0
    var maxSum = 0
    var left = 0

    for (right <- arr.indices) {
      windowSum += arr(right)

      if (right - left + 1 == k) {
        maxSum = Math.max(maxSum, windowSum)
        windowSum -= arr(left)
        left += 1
      }
    }

    maxSum
  }
}

Kotlin

class Solution {
  fun maxSum(arr: IntArray, k: Int): Int {
    var windowSum = 0
    var maxSum = 0
    var left = 0

    for (right in arr.indices) {
      windowSum += arr[right]

      if (right - left + 1 == k) {
        maxSum = maxOf(maxSum, windowSum)
        windowSum -= arr[left++]
      }
    }

    return maxSum
  }
}

Ruby

class Solution
  def max_sum(arr, k)
    window_sum = 0
    max_sum = 0
    left = 0

    (0...arr.length).each do |right|
      window_sum += arr[right]

      if right - left + 1 == k
        max_sum = [max_sum, window_sum].max
        window_sum -= arr[left]
        left += 1
      end
    end

    max_sum
  end
end

Swift

class Solution {
    func maxSum(_ arr: [Int], _ k: Int) -> Int {
        var windowSum = 0
        var maxSum = 0
        var left = 0

        for right in 0..<arr.count {
            windowSum += arr[right]

            if right - left + 1 == k {
                maxSum = max(maxSum, windowSum)
                windowSum -= arr[left]
                left += 1
            }
        }

        return maxSum
    }
}

Rust

impl Solution {
    pub fn max_sum(&self, arr: Vec<i32>, k: i32) -> i32 {
        let mut window_sum = 0;
        let mut max_sum = 0;
        let mut left = 0;

        for right in 0..arr.len() {
            window_sum += arr[right];

            if (right - left + 1) == k as usize {
                max_sum = max_sum.max(window_sum);
                window_sum -= arr[left];
                left += 1;
            }
        }

        max_sum
    }
}

C#

public class Solution {
    public int MaxSum(int[] arr, int k) {
        int windowSum = 0, maxSum = 0;
        int left = 0;

        for (int right = 0; right < arr.Length; right++) {
            windowSum += arr[right];

            if (right - left + 1 == k) {
                maxSum = Math.Max(maxSum, windowSum);
                windowSum -= arr[left++];
            }
        }

        return maxSum;
    }
}

Dart

import 'dart:math';

class Solution {
  int maxSum(List<int> arr, int k) {
    int windowSum = 0, maxSum = 0;
    int left = 0;

    for (int right = 0; right < arr.length; right++) {
      windowSum += arr[right];

      if (right - left + 1 == k) {
        maxSum = max(maxSum, windowSum);
        windowSum -= arr[left++];
      }
    }

    return maxSum;
  }
}

PHP

class Solution {
    public function maxSum(array $arr, int $k): int {
        $windowSum = 0;
        $maxSum = 0;
        $left = 0;

        for ($right = 0; $right < count($arr); $right++) {
            $windowSum += $arr[$right];

            if ($right - $left + 1 == $k) {
                $maxSum = max($maxSum, $windowSum);
                $windowSum -= $arr[$left++];
            }
        }

        return $maxSum;
    }
}

Key Takeaways

• The sliding window technique converts O(n * k) brute force into O(n) by reusing the sum from the previous window, adjusting only the element that leaves and the element that enters.
• The window condition right - left + 1 == k ensures you only record and slide once the window has exactly k elements. Getting this check wrong is the most common source of bugs.
• This fixed-width sliding window pattern is the foundation for variable-width window problems. Once you internalize the expand-check-shrink loop, harder variations become easier to reason about.
• Always update maxSum before shrinking the window. Reversing the order means you lose the current window's sum before comparing it.
• Test with k = 1 and k = array length as boundary cases. They verify your window logic handles the smallest and largest possible windows correctly.

Related Problems

Once you're comfortable with this problem, these build on the same sliding window foundation:

• Average of contiguous subarrays of size k (same pattern, different aggregation)
• Longest substring without repeated characters (variable-width window)
• Minimum window substring (variable-width with a frequency map)

This problem and hundreds of others are available on Firecode, where over 50,000 engineers have prepared for technical interviews and landed roles at top companies. Consistent practice with problems like this builds the pattern recognition that makes interview day feel routine.