We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Subarray Sum With Length Divisible by K

Number: 3653

Difficulty: Medium

Paid? No

Companies: Bloomberg

Problem Description

Given an integer array nums and an integer k, find the maximum sum of any subarray whose length is divisible by k.

Key Insights

  • Use prefix sums to quickly compute the sum of any subarray.
  • For a subarray from index i to j, if (j - i) is divisible by k, then the corresponding prefix sum indices satisfy: (prefixIndex j - prefixIndex i) where j and i have the same remainder modulo k.
  • Maintain the minimum prefix sum for each remainder as you iterate through the array.
  • The answer at each index j can be calculated as the current prefix sum minus the minimum prefix sum previously seen with the same remainder.

Space and Time Complexity

Time Complexity: O(n), where n is the number of elements in nums. Space Complexity: O(k), since we store the minimum prefix sums for each remainder modulo k.

Solution

We first compute cumulative prefix sums while processing the array. Since a subarray sum can be represented as the difference between two prefix sums, we require that the two corresponding indices share the same remainder modulo k for the subarray’s length to be divisible by k. As we iterate over the array, we keep track of the smallest prefix sum encountered for each remainder modulo k. For every new prefix sum, we check if subtracting the stored minimum for the same remainder provides a candidate for our answer. Finally, we update the minimum prefix sum for that remainder. This approach ensures that all valid subarrays are considered and the overall maximum sum is retained.

Code Solutions

# Python solution with detailed comments

def maxSubarraySumDivK(nums, k):
    # Initialize variables: prefix is the running sum
    # min_prefix_mod stores the minimum prefix sum for each modulo remainder
    prefix = 0
    # Using a large positive number for initial comparison, except for remainder 0
    min_prefix_mod = [float('inf')] * k
    min_prefix_mod[0] = 0  # Base case: prefix sum 0 at index 0 has remainder 0
    max_sum = -float('inf')
    
    # Iterate over nums to compute prefix sums on the fly
    for num in nums:
        prefix += num
        # Compute remainder; ensure it is non-negative
        mod = prefix % k
        # Candidate subarray sum: current prefix minus the smallest prefix sum 
        # with the same remainder encountered so far
        candidate = prefix - min_prefix_mod[mod]
        max_sum = max(max_sum, candidate)
        # Update the minimum prefix sum for the current remainder
        min_prefix_mod[mod] = min(min_prefix_mod[mod], prefix)
    
    return max_sum

# Example usage:
print(maxSubarraySumDivK([1,2], 1))         # Expected output: 3
print(maxSubarraySumDivK([-1,-2,-3,-4,-5], 4)) # Expected output: -10
print(maxSubarraySumDivK([-5,1,2,-3,4], 2))   # Expected output: 4
← Back to All Questions