LeetCode Problem 3381

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Prefix Sum

Solution

LeetCode 3381 - Maximum Subarray Sum With Length Divisible by K

Problem Understanding

We are given an integer array nums and an integer k. We must find a contiguous subarray whose length is divisible by k, and among all such valid subarrays, return the maximum possible sum.

A subarray is a contiguous segment of the array. If a subarray starts at index l and ends at index r, then:

• Its length is r - l + 1
• Its sum is the sum of all elements from l through r

The key constraint is that the subarray length must be divisible by k.

For example, if k = 2, then valid lengths are 2, 4, 6, .... If k = 3, then valid lengths are 3, 6, 9, ....

The input size is large:

• 1 <= k <= nums.length <= 2 * 10^5
• -10^9 <= nums[i] <= 10^9

These constraints immediately rule out any solution that examines all possible subarrays. There are O(n²) possible subarrays, which would be far too slow when n = 200,000.

Another important observation is that array values may be negative. Therefore:

• The answer is not necessarily positive.
• We cannot assume extending a subarray improves the result.
• We must correctly handle cases where every valid subarray has a negative sum.

Some important edge cases include:

• Arrays consisting entirely of negative numbers.
• k = 1, where every subarray length is valid.
• k = n, where only the entire array is valid.
• Situations where the optimal answer comes from a long subarray rather than a short one.
• Large positive and negative values that require 64-bit integer arithmetic.

Approaches

Brute Force

A straightforward solution is to consider every possible subarray.

For each starting index i, we can extend the ending index j and maintain the running sum. Whenever the length (j - i + 1) is divisible by k, we compare the sum against the current answer.

This approach is correct because it explicitly checks every valid subarray and therefore cannot miss the optimum.

However, there are O(n²) subarrays. With n = 200,000, this becomes approximately 4 × 10^10 possibilities, which is completely infeasible.

Key Insight

Let prefix[i] denote the sum of the first i elements.

Then the sum of a subarray [l, r] is:

$$prefix[r+1] - prefix[l]$$

The length of that subarray is:

$$(r+1) - l$$

We need this length to be divisible by k:

$$(r+1) - l \equiv 0 \pmod{k}$$

Rearranging:

$$l \equiv r+1 \pmod{k}$$

This is the crucial observation.

For every prefix position i = r + 1, we need a previous prefix position j such that:

$$j \equiv i \pmod{k}$$

The subarray sum becomes:

$$prefix[i] - prefix[j]$$

To maximize this value, we want the smallest possible prefix[j] among all previous positions having the same remainder modulo k.

Therefore, while scanning prefix positions from left to right:

• Group prefix indices by index % k.
• For each remainder, keep the minimum prefix sum seen so far.
• When visiting a new prefix sum, compute the best subarray ending here using that minimum prefix.

This transforms the problem into a single linear scan.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Checks every possible subarray
Optimal	O(n)	O(k)	Uses prefix sums and minimum prefix values per remainder class

Algorithm Walkthrough

1. Create an array min_prefix of size k.

min_prefix[r] will store the smallest prefix sum encountered so far at a prefix index whose modulo class is r. 2. Initialize all entries to positive infinity.

This indicates that no prefix index of that remainder class has been seen yet. 3. Set the prefix sum to 0.

The empty prefix corresponds to index 0, whose remainder is 0 % k. 4. Record the empty prefix.

Set:

min_prefix[0] = 0

5. Scan through the array from left to right.

After processing element nums[i], update the running prefix sum. 6. Let position = i + 1.

This is the prefix index corresponding to the current prefix sum. 7. Compute:

remainder = position % k

8. If a previous prefix with the same remainder exists, compute a candidate answer:

candidate = prefix_sum - min_prefix[remainder]

This corresponds to the maximum-sum subarray ending at the current position whose length is divisible by k. 9. Update the global answer with the candidate value. 10. Update the minimum prefix sum for this remainder:

min_prefix[remainder] =
    min(min_prefix[remainder], prefix_sum)

This ensures future positions can use the smallest prefix sum available. 11. Continue until the entire array has been processed. 12. Return the maximum answer found.

Why it works

For a subarray ending at prefix position i, the length divisibility condition requires the starting prefix position j to satisfy:

$$j \equiv i \pmod{k}$$

Among all such valid j, the subarray sum equals:

$$prefix[i] - prefix[j]$$

Since prefix[i] is fixed while processing position i, the maximum possible sum is obtained by choosing the smallest available prefix[j] with the same modulo class. The algorithm maintains exactly this value for every remainder class, so every valid subarray is considered implicitly and the optimal one is guaranteed to be found.

Python Solution

from typing import List

class Solution:
    def maxSubarraySum(self, nums: List[int], k: int) -> int:
        INF = float("inf")

        min_prefix = [INF] * k
        min_prefix[0] = 0

        prefix_sum = 0
        answer = -10**30

        for i, num in enumerate(nums):
            prefix_sum += num

            remainder = (i + 1) % k

            if min_prefix[remainder] != INF:
                answer = max(
                    answer,
                    prefix_sum - min_prefix[remainder]
                )

            min_prefix[remainder] = min(
                min_prefix[remainder],
                prefix_sum
            )

        return answer

The implementation follows the mathematical derivation directly.

prefix_sum stores the running prefix total. The array min_prefix maintains the minimum prefix sum seen for each modulo class of the prefix index.

At every position, we determine which modulo class the current prefix index belongs to. Any valid subarray ending here must start from a previous prefix index with the same modulo class. Therefore, subtracting the smallest such prefix sum gives the best possible subarray ending at this position.

After evaluating the candidate answer, we update the stored minimum prefix sum for the current remainder class. This ensures future positions can benefit from it.

Because each element is processed exactly once and every operation inside the loop is constant time, the algorithm runs in linear time.

Go Solution

func maxSubarraySum(nums []int, k int) int64 {
	const INF int64 = 1 << 60

	minPrefix := make([]int64, k)
	for i := range minPrefix {
		minPrefix[i] = INF
	}
	minPrefix[0] = 0

	var prefixSum int64 = 0
	var answer int64 = -(1 << 60)

	for i, num := range nums {
		prefixSum += int64(num)

		remainder := (i + 1) % k

		if minPrefix[remainder] != INF {
			candidate := prefixSum - minPrefix[remainder]
			if candidate > answer {
				answer = candidate
			}
		}

		if prefixSum < minPrefix[remainder] {
			minPrefix[remainder] = prefixSum
		}
	}

	return answer
}

The Go implementation is essentially identical to the Python version.

The primary difference is the use of int64 throughout the computation. Since nums[i] can be as large as 10^9 and there can be up to 200,000 elements, prefix sums may reach approximately 2 × 10^14, which exceeds 32-bit integer limits. Using int64 guarantees correctness.

The minPrefix slice stores the minimum prefix sum for each remainder class, and all updates remain constant time.

Worked Examples

Example 1

Input:

nums = [1, 2]
k = 1

Initial state:

Position	Prefix Sum	Remainder	min_prefix[0]	Answer
Start	0	0	0	-∞

Processing:

Position	Prefix Sum	Remainder	Candidate	Answer
1	1	0	1 - 0 = 1	1
2	3	0	3 - 0 = 3	3

Final answer:

3

Example 2

Input:

nums = [-1,-2,-3,-4,-5]
k = 4

Initial:

min_prefix = [0, inf, inf, inf]

Position	Prefix Sum	Remainder	Candidate	Answer
1	-1	1	N/A	-∞
2	-3	2	N/A	-∞
3	-6	3	N/A	-∞
4	-10	0	-10 - 0 = -10	-10
5	-15	1	-15 - (-1) = -14	-10

Final answer:

-10

Example 3

Input:

nums = [-5,1,2,-3,4]
k = 2

Initial:

min_prefix = [0, inf]

Position	Prefix Sum	Remainder	Candidate	Answer
1	-5	1	N/A	-∞
2	-4	0	-4 - 0 = -4	-4
3	-2	1	-2 - (-5) = 3	3
4	-5	0	-5 - 0 = -5	3
5	-1	1	-1 - (-5) = 4	4

Final answer:

4

The corresponding subarray is:

[1, 2, -3, 4]

with length 4, which is divisible by 2.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each element is processed exactly once
Space	O(k)	One minimum prefix value is stored for each remainder class

The algorithm performs a single pass through the array. Every iteration executes only a handful of arithmetic operations and array accesses, all of which are constant time. The auxiliary storage consists solely of the min_prefix array containing k entries.

Test Cases

s = Solution()

assert s.maxSubarraySum([1, 2], 1) == 3          # example 1
assert s.maxSubarraySum([-1, -2, -3, -4, -5], 4) == -10  # example 2
assert s.maxSubarraySum([-5, 1, 2, -3, 4], 2) == 4       # example 3

assert s.maxSubarraySum([5], 1) == 5            # single element
assert s.maxSubarraySum([-5], 1) == -5          # single negative element

assert s.maxSubarraySum([1, 2, 3, 4], 4) == 10  # only whole array valid

assert s.maxSubarraySum([-1, -2, -3], 1) == -1  # best single element

assert s.maxSubarraySum([1, -100, 100, 100], 2) == 200
# optimal length-2 subarray

assert s.maxSubarraySum([2, 2, 2, 2, 2], 2) == 10
# whole array length not divisible by 2? best valid length is 4 -> sum 8

assert s.maxSubarraySum([2, 2, 2, 2], 2) == 8
# entire array

assert s.maxSubarraySum([10, -1, -1, 10], 2) == 18
# length-4 subarray beats any length-2 option

assert s.maxSubarraySum([-10, 100, -10, 100, -10], 2) == 180
# longer valid subarray produces optimum

Test Summary

Test	Why
[1,2], k=1	Basic example
[-1,-2,-3,-4,-5], k=4	All negative values
[-5,1,2,-3,4], k=2	Mixed positive and negative values
[5], k=1	Smallest valid input
[-5], k=1	Single negative element
[1,2,3,4], k=4	Only whole array is valid
[-1,-2,-3], k=1	Maximum among all negative subarrays
[1,-100,100,100], k=2	Best answer comes from interior subarray
[2,2,2,2], k=2	Entire array optimal
[10,-1,-1,10], k=2	Longer valid subarray wins
[-10,100,-10,100,-10], k=2	Mixed signs with large positive gain

Edge Cases

All Numbers Are Negative

A common mistake is to assume the answer is always non-negative and initialize the result to 0. If every valid subarray has a negative sum, that would produce an incorrect answer.

For example:

nums = [-1,-2,-3,-4]
k = 4

The correct answer is -10. The implementation avoids this bug by initializing the answer to a very small value and allowing negative results to become the final answer.

k Equals 1

When k = 1, every subarray length is valid because every integer is divisible by 1.

The problem effectively becomes finding the maximum subarray sum, but the algorithm still works naturally. Every prefix index has remainder 0, so the solution continuously compares the current prefix sum against the minimum prefix sum seen so far.

k Equals nums.length

When k equals the array length, the only valid subarray length is exactly n.

In this situation, the optimal answer must be the sum of the entire array. The modulo condition ensures that only prefix indices separated by exactly n positions can contribute, and the algorithm correctly discovers that unique valid subarray.

Large Prefix Sums

Because each element may be as large as 10^9 and there can be up to 200,000 elements, prefix sums can reach roughly:

2 × 10^5 × 10^9 = 2 × 10^14

This exceeds 32-bit integer limits. The Go implementation uses int64, and Python integers automatically support arbitrary precision, ensuring no overflow occurs.