Skip to main content
Talentd

Maximum Subarray Sum With Length Divisible by K - Solution & Explanation

MediumArrayHash TablePrefix Sum10 min readAsked at: Amazon, Meta, Google +1
Practice this problem

Problem Statement

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

Return the maximum sum of a subarray of nums, such that the size of the subarray is divisible by k.

 

Example 1:

Input: nums = [1,2], k = 1

Output: 3

Explanation:

The subarray [1, 2] with sum 3 has length equal to 2 which is divisible by 1.

Example 2:

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

Output: -10

Explanation:

The maximum sum subarray is [-1, -2, -3, -4] which has length equal to 4 which is divisible by 4.

Example 3:

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

Output: 4

Explanation:

The maximum sum subarray is [1, 2, -3, 4] which has length equal to 4 which is divisible by 2.

 

Constraints:

  • 1 <= k <= nums.length <= 2 * 105
  • -109 <= nums[i] <= 109

Approach Overview

Problem Overview: Given an integer array and an integer k, compute the maximum possible sum of a subarray whose length is divisible by k. The constraint on length means if a subarray starts at index j and ends at i, the condition (i - j) % k == 0 must hold.

Approach 1: Brute Force Enumeration (O(n²) time, O(1) space)

Enumerate every possible subarray and compute its sum. While expanding a subarray from index i to j, track the current length. Whenever the length satisfies (j - i + 1) % k == 0, update the maximum sum. Prefix sums can slightly simplify the sum calculation, but the algorithm still checks all O(n²) ranges. This approach demonstrates the core condition on subarray length but becomes too slow when n grows beyond a few thousand.

Approach 2: Prefix Sum + Modulo Enumeration (O(n) time, O(k) space)

The key observation: if a subarray from j to i-1 has length divisible by k, then i % k == j % k. Build a prefix sum array where prefix[i] is the sum of the first i elements. The subarray sum becomes prefix[i] - prefix[j]. For each remainder r = i % k, track the smallest prefix sum previously seen at an index with the same remainder. When you revisit that remainder, compute prefix[i] - minPrefix[r] to get the best subarray ending at i whose length is divisible by k. Update the maximum and refresh the stored minimum prefix if the current one is smaller. This turns the problem into a single pass over the array with constant-time updates.

The data structure holding the minimum prefix per remainder can be a simple array of size k or a hash table. Each iteration performs constant work: compute the new prefix sum, check the remainder group, update the answer, and maintain the minimum prefix value.

This technique relies on the interaction between index arithmetic and cumulative sums. Similar patterns appear in many array problems where constraints apply to subarray length, parity, or divisibility.

Recommended for interviews: Prefix Sum + Modulo Enumeration. Interviewers expect you to move from the quadratic enumeration idea to the prefix-sum observation that indices with the same i % k form valid boundaries. The optimized solution runs in O(n) time and uses only O(k) additional space, showing both algorithmic insight and familiarity with prefix sum patterns.

Solution

According to the problem description, for a subarray's length to be divisible by k, it is equivalent to requiring that for subarray nums[i+1 ldots j], we have i bmod k = j bmod k.

We can enumerate the right endpoint j of the subarray and use an array f of length k to record the minimum prefix sum for each modulo k. Initially, f[k-1] = 0, indicating that the prefix sum at index -1 is 0.

Then for the current right endpoint j with prefix sum s, we can calculate the maximum sum of subarrays ending at j with length divisible by k as s - f[j bmod k], and update the answer accordingly. At the same time, we need to update f[j bmod k] to be the minimum of the current prefix sum s and f[j bmod k].

After the enumeration is complete, return the answer.

The time complexity is O(n) and the space complexity is O(k), where n is the length of the array nums.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Subarray EnumerationO(n²)O(1)Understanding the problem constraint or when input size is very small
Prefix Sum + Modulo GroupingO(n)O(k)Optimal solution for large arrays; standard interview approach
Prefix Sum + Hash MapO(n)O(k)Useful when k is large or when implementing remainder tracking dynamically

Video Solution

Maximum Subarray Sum With Length Divisible by K | Simplified Kadane's Algo | Leetcode 3381 | MIK • codestorywithMIK • 12,186 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Maximum Subarray Sum With Length Divisible by K easy or hard?
The problem is generally rated Medium because the brute-force idea is straightforward but the optimal solution requires recognizing a prefix-sum and modulo pattern. Once the relationship between index remainders and valid subarray lengths is identified, the implementation becomes a linear-time scan.
Maximum Subarray Sum With Length Divisible by K Python/Java solution
Implement the prefix sum + modulo grouping approach. Maintain an array or map storing the minimum prefix sum for each remainder i % k. While iterating through the array, compute the current prefix sum, check the stored minimum for that remainder, update the maximum subarray sum, and refresh the minimum prefix if needed.
How to solve Maximum Subarray Sum With Length Divisible by K in O(n)?
Compute a running prefix sum while iterating through the array. For each index i, calculate r = i % k and maintain the smallest prefix sum previously seen with the same remainder. The candidate subarray sum becomes prefix[i] minus that stored minimum. Updating these values during a single traversal yields an O(n) solution.
What is the best approach for Maximum Subarray Sum With Length Divisible by K?
The most efficient approach uses prefix sums combined with grouping indices by their modulo k value. If two prefix indices share the same remainder i % k, the subarray between them has length divisible by k. By tracking the minimum prefix sum for each remainder, you can compute the maximum subarray sum in O(n) time and O(k) space.
Is Maximum Subarray Sum With Length Divisible by K asked at Google/Amazon/Meta?
Variants of prefix sum and subarray divisibility problems appear frequently in interviews at companies like Google, Amazon, and Meta. Problems involving prefix sums, modulo grouping, and maximum subarray calculations are common because they test pattern recognition and optimization skills.
What data structure is used in Maximum Subarray Sum With Length Divisible by K?
The solution primarily uses a prefix sum array and a structure to track the minimum prefix value for each remainder group. This structure is typically an array of size k or a hash table mapping remainder values to the smallest prefix sum seen so far.
What is the time complexity of Maximum Subarray Sum With Length Divisible by K?
The optimal solution runs in O(n) time using a single pass through the array with prefix sums and remainder tracking. Space complexity is O(k) because the algorithm stores the minimum prefix sum for each modulo class from 0 to k-1.

Ready to solve this problem?

Practice Maximum Subarray Sum With Length Divisible by K with our built-in code editor and test cases.

Practice on FleetCode
Previous

Subarray Sums Divisible by K