Problem Description

You are given an array of integers nums and an integer k.

Your task is to find a contiguous subarray whose length is divisible by k that has the maximum possible sum. The subarray must be non-empty.

For example:

• If k = 3, valid subarray lengths would be 3, 6, 9, 12, etc.
• If k = 2, valid subarray lengths would be 2, 4, 6, 8, etc.

The goal is to return the maximum sum among all such valid subarrays.

Key constraints:

• The subarray must be contiguous (elements must be adjacent in the original array)
• The length of the subarray must be exactly divisible by k (length % k == 0)
• You need to find the maximum sum possible among all valid subarrays

Intuition

To find the maximum sum of a subarray with length divisible by k, we need to think about how to efficiently check all possible subarrays that meet this constraint.

A key observation is that if we have a subarray from index i to index j, its length is j - i + 1. For this length to be divisible by k, we need (j - i + 1) % k == 0, which means j % k == (i - 1) % k.

This suggests we can use prefix sums combined with modular arithmetic. If we compute the cumulative sum up to each position, then the sum of a subarray from position i to j equals prefix_sum[j] - prefix_sum[i-1].

The critical insight is that we only need to track the minimum prefix sum for each possible remainder when divided by k. We can maintain an array f of size k where f[r] stores the minimum prefix sum seen so far at positions whose index modulo k equals r.

As we iterate through the array:

1. We calculate the running sum s
2. For the current position i, we check what's the minimum prefix sum at positions that would give us a valid subarray length (positions with remainder i % k)
3. The maximum subarray sum ending at position i with valid length is s - f[i % k]
4. We update f[i % k] with the minimum between its current value and our current sum s

By initializing f[-1] = 0 (which corresponds to f[k-1] = 0), we handle the case where we start from the beginning of the array. This allows us to consider subarrays that start at index 0.

This approach efficiently finds the maximum sum in O(n) time by avoiding the need to check every possible subarray explicitly.

Learn more about Prefix Sum patterns.

Solution Approach

Let's walk through the implementation step by step:

1. Initialize the tracking array:

f = [inf] * k

We create an array f of size k initialized with infinity. This array tracks the minimum prefix sum for each remainder class modulo k. We use infinity as the initial value so any actual sum will be smaller.

2. Set up initial values:

ans = -inf
s = f[-1] = 0

• ans is initialized to negative infinity to track the maximum subarray sum found
• s is our running prefix sum, starting at 0
• f[-1] (which is f[k-1]) is set to 0, representing an empty prefix before the array starts

3. Main iteration through the array:

for i, x in enumerate(nums):
    s += x
    ans = max(ans, s - f[i % k])
    f[i % k] = min(f[i % k], s)

For each element at index i:

• Update the prefix sum: Add the current element x to our running sum s
• Check for maximum subarray: Calculate s - f[i % k]
  • This gives us the sum of a subarray ending at position i with length divisible by k
  • We subtract the minimum prefix sum that has the same remainder as i when divided by k
  • This ensures the subarray length between those positions is divisible by k
• Update the answer: Keep track of the maximum sum found so far
• Update the minimum prefix sum: Store the minimum prefix sum for this remainder class

Why this works:

• When we're at position i with remainder r = i % k, we look for the minimum prefix sum at a previous position j where j % k == r
• The subarray from position j+1 to position i has length i - j, which is divisible by k since both i and j have the same remainder modulo k
• By keeping only the minimum prefix sum for each remainder class, we maximize the subarray sum when we subtract it from the current prefix sum

4. Return the result:

return ans

The algorithm runs in O(n) time with O(k) extra space, making it efficient for finding the maximum sum of a subarray with length divisible by k.

Example Walkthrough

Let's walk through an example with nums = [1, 2, -1, -2, 3, 4] and k = 3.

We need to find a contiguous subarray whose length is divisible by 3 (length could be 3, 6, etc.) with maximum sum.

Initial Setup:

• f = [inf, inf, inf] (array of size k=3)
• ans = -inf (to track maximum sum)
• s = 0 (running prefix sum)
• f[-1] = f[2] = 0 (initialize last position)

Iteration Process:

i = 0, x = 1:

• s = 0 + 1 = 1
• i % k = 0 % 3 = 0
• Check: s - f[0] = 1 - inf = -inf
• Update: ans = max(-inf, -inf) = -inf
• Update: f[0] = min(inf, 1) = 1
• State: f = [1, inf, 0], ans = -inf

i = 1, x = 2:

• s = 1 + 2 = 3
• i % k = 1 % 3 = 1
• Check: s - f[1] = 3 - inf = -inf
• Update: ans = max(-inf, -inf) = -inf
• Update: f[1] = min(inf, 3) = 3
• State: f = [1, 3, 0], ans = -inf

i = 2, x = -1:

• s = 3 + (-1) = 2
• i % k = 2 % 3 = 2
• Check: s - f[2] = 2 - 0 = 2 (This represents subarray [1, 2, -1] with length 3)
• Update: ans = max(-inf, 2) = 2
• Update: f[2] = min(0, 2) = 0
• State: f = [1, 3, 0], ans = 2

i = 3, x = -2:

• s = 2 + (-2) = 0
• i % k = 3 % 3 = 0
• Check: s - f[0] = 0 - 1 = -1 (This represents subarray [2, -1, -2] with length 3)
• Update: ans = max(2, -1) = 2
• Update: f[0] = min(1, 0) = 0
• State: f = [0, 3, 0], ans = 2

i = 4, x = 3:

• s = 0 + 3 = 3
• i % k = 4 % 3 = 1
• Check: s - f[1] = 3 - 3 = 0 (This represents subarray [-1, -2, 3] with length 3)
• Update: ans = max(2, 0) = 2
• Update: f[1] = min(3, 3) = 3
• State: f = [0, 3, 0], ans = 2

i = 5, x = 4:

• s = 3 + 4 = 7
• i % k = 5 % 3 = 2
• Check: s - f[2] = 7 - 0 = 7 (This represents entire array [1, 2, -1, -2, 3, 4] with length 6)
• Update: ans = max(2, 7) = 7
• Update: f[2] = min(0, 7) = 0
• State: f = [0, 3, 0], ans = 7

Result: The maximum sum is 7, from the entire array with length 6 (divisible by 3).

The algorithm correctly identified two valid subarrays:

• [1, 2, -1] with sum = 2 and length = 3
• [1, 2, -1, -2, 3, 4] with sum = 7 and length = 6

Both have lengths divisible by k=3, and the maximum sum is 7.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n) where n is the length of the input array nums.

The algorithm iterates through the array exactly once with a single for loop. Within each iteration, all operations are constant time:

• Array access and update operations: f[i % k] takes O(1)
• Addition operation: s += x takes O(1)
• Max and min comparisons: max(ans, s - f[i % k]) and min(f[i % k], s) take O(1)

Since we perform n iterations with O(1) work per iteration, the total time complexity is O(n).

Space Complexity: O(k) where k is the input parameter.

The algorithm uses:

• Array f of size k to store minimum prefix sums for each remainder class modulo k: O(k)
• Variables ans and s for tracking the maximum sum and current prefix sum: O(1)
• Loop variables i and x: O(1)

The dominant space usage is the array f, making the overall space complexity O(k).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Off-by-One Error with Index Mapping

Pitfall: The most common mistake is misunderstanding how the remainder classes work with array indices. When we're at index i, we need to look for previous positions with the same remainder class to ensure the subarray length is divisible by k. However, the tricky part is handling the case where we want a subarray starting from index 0.

Example of the problem:

# Incorrect approach - doesn't handle subarrays from index 0
min_prefix_sum = [float('inf')] * k
for i, x in enumerate(nums):
    prefix_sum += x
    if min_prefix_sum[i % k] != float('inf'):  # Wrong check!
        max_sum = max(max_sum, prefix_sum - min_prefix_sum[i % k])
    min_prefix_sum[i % k] = min(min_prefix_sum[i % k], prefix_sum)

Why it fails: For a subarray starting at index 0 and ending at index i where (i+1) % k == 0, we need to subtract 0 from the prefix sum. But if we don't initialize properly, we'll never consider these valid subarrays.

Solution: Initialize min_prefix_sum[k-1] = 0 before the loop. This represents a "virtual" position at index -1, which has remainder k-1 when considering modulo k arithmetic. This allows us to correctly handle subarrays starting from index 0.

2. Incorrect Order of Operations

Pitfall: Updating the minimum prefix sum before calculating the maximum subarray sum for the current position.

Incorrect code:

for i, x in enumerate(nums):
    prefix_sum += x
    min_prefix_sum[i % k] = min(min_prefix_sum[i % k], prefix_sum)  # Updated too early!
    max_sum = max(max_sum, prefix_sum - min_prefix_sum[i % k])  # Now always gets 0 or positive

Why it fails: If we update min_prefix_sum[i % k] before calculating the maximum sum, we're potentially using the current position's prefix sum to calculate a subarray of length 0 (when prefix_sum - prefix_sum = 0), which violates the non-empty subarray requirement.

Solution: Always calculate the potential maximum sum first, then update the minimum prefix sum:

max_sum = max(max_sum, prefix_sum - min_prefix_sum[i % k])  # Calculate first
min_prefix_sum[i % k] = min(min_prefix_sum[i % k], prefix_sum)  # Update after

3. Forgetting Edge Cases with Small Arrays

Pitfall: Not handling cases where the array length is smaller than k.

Example scenario:

• nums = [1, 2], k = 3
• The only valid subarray length would be 3, but the array only has 2 elements
• The algorithm should return negative infinity or handle this gracefully

Solution: The current implementation handles this correctly by initializing max_sum = float('-inf'). If no valid subarray is found, it returns negative infinity. However, depending on problem requirements, you might need to explicitly check and handle this case:

if len(nums) < k:
    return float('-inf')  # or handle as per problem requirements