Jobs

Interviews

Discussions

Maximum Subarray Sum With Length Divisible by K

Medium

Asked by:

8 views

Topics:

ArraysDynamic Programming

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 * 10⁵
-10⁹ <= nums[i] <= 10⁹

Try coding it in LeetCode

Maximum Subarray Sum With Length Divisible by K

Medium

Asked by:

8 views

Topics:

ArraysDynamic Programming

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 * 10⁵
-10⁹ <= nums[i] <= 10⁹

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the possible ranges for the integer values in the input array and the value of K?
Can the input array be empty, or can K be zero?
If no subarray with a length divisible by K has a positive sum, what value should I return?
Does the problem require finding *any* maximum subarray sum with length divisible by K, or the *first* such subarray encountered, or the *longest* if there are multiple maximum sums?
Is the input array guaranteed to contain only integers, or could there be other data types?

Brute Force Solution

Approach

The brute force strategy involves checking every possible consecutive group of numbers within the given set. For each group, we determine if the group's size is evenly divisible by a specific number, and if so, calculate and keep track of the group's total sum.

Here's how the algorithm would work step-by-step:

Begin with the first number in the set and consider it as a group by itself.
Check if the size of the current group is divisible by the given number.
If it is, add all the numbers in the group to get the group's total sum.
Keep track of the largest group total sum you have seen so far.
Next, consider the first two numbers as a group, then the first three, and so on, always checking the divisibility and summing as before.
Once you have considered all possible groups starting from the first number, move on to the second number and repeat the process by considering groups of increasing size from there.
Continue this process, shifting the starting position one number at a time, until you have considered all possible consecutive groups within the set.
In the end, the largest group total sum you kept track of is your answer.

Code Implementation

def max_subarray_sum_divisible_by_k_brute_force(number_list, divisor):
    maximum_sum = float('-inf')

    for start_index in range(len(number_list)):
        for end_index in range(start_index, len(number_list)):
            # Creating the sub array that ends at end_index
            sub_array = number_list[start_index:end_index + 1]

            # Check if the sub array length is divisible by k
            if len(sub_array) % divisor == 0:

                current_sum = sum(sub_array)
                # Keep track of the largest sum we have found
                if current_sum > maximum_sum:

                    maximum_sum = current_sum

    return maximum_sum

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through all possible subarrays of the input array of size n. For each starting index i, it considers subarrays of increasing length up to n-i. This nested iteration results in approximately n*(n+1)/2 operations. Ignoring lower-order terms and constants, the time complexity simplifies to O(n²).

Space Complexity

O(1) – The provided brute force algorithm only uses a few variables to store the current group's sum and the maximum sum found so far. These variables consume a constant amount of space, irrespective of the input array's size (N). The algorithm doesn't create any auxiliary data structures like arrays, lists, or hash maps to store intermediate results or track visited elements. Therefore, the auxiliary space complexity is O(1).

Optimal Solution

Approach

The goal is to find the biggest possible sum from a continuous section of numbers where the length of that section is perfectly divisible by K. Instead of checking every possible section, we use a clever trick to keep track of potential starting points that might lead to the best answer.

Here's how the algorithm would work step-by-step:

First, calculate a running sum of all the numbers. For each number, also figure out what the remainder is when you divide the sum by K.
Keep track of the *first* time you see each remainder value. These are potentially good starting points for our sections because subtracting these earlier sums will result in a number that is divisible by K.
For each position, calculate the current running sum's remainder.
Subtract the running sum that gave us the first occurrence of that remainder from the current running sum. This result gives you a candidate sum for a section of numbers that has length divisible by K.
Keep track of the biggest sum you've found so far. As you calculate these candidate sums, update the maximum if you find a bigger one.
By remembering only the first time we see each remainder, we can quickly calculate the sums of sections divisible by K without trying every single possible section.

Code Implementation

def max_subarray_sum_divisible_by_k(numbers, k):
    maximum_sum = float('-inf')
    current_running_sum = 0
    remainder_first_occurrence = {}

    # Initialize remainder 0 to index -1 to handle subarrays
    # starting from the beginning of the input array
    remainder_first_occurrence[0] = -1

    for index, number in enumerate(numbers):
        current_running_sum += number
        current_remainder = current_running_sum % k

        # Store the first occurrence of each remainder to calculate
        # subarray sums divisible by k.
        if current_remainder not in remainder_first_occurrence:
            remainder_first_occurrence[current_remainder] = index

        # Calculate the subarray sum and update the maximum sum
        # if a larger sum is found
        else:
            subarray_sum = current_running_sum - \
                sum(numbers[remainder_first_occurrence[current_remainder]+1:index+1])

            subarray_sum = current_running_sum - \
                sum(numbers[remainder_first_occurrence[current_remainder]+1:index+1])

            maximum_sum = max(maximum_sum, current_running_sum - numbers[remainder_first_occurrence[current_remainder]+1])

            subarray_sum = current_running_sum - numbers[remainder_first_occurrence[current_remainder]+1]
            maximum_sum = max(maximum_sum, subarray_sum)

            start_index = remainder_first_occurrence[current_remainder] + 1
            end_index = index + 1
            subarray_sum = sum(numbers[start_index:end_index])
            maximum_sum = max(maximum_sum, subarray_sum)

            maximum_sum = max(maximum_sum, current_running_sum - sum(numbers[:remainder_first_occurrence[current_remainder] + 1]))

            # Calculate the subarray sum using the prefix sum technique
            subarray_sum = current_running_sum - sum(numbers[0 : remainder_first_occurrence[current_remainder] + 1])
            maximum_sum = max(maximum_sum, subarray_sum)

            subarray_sum = current_running_sum - sum(numbers[:remainder_first_occurrence[current_remainder] + 1])

            # Ensure the length is divisible by k
            if (index - remainder_first_occurrence[current_remainder]) % k == 0:
                maximum_sum = max(maximum_sum, current_running_sum - sum(numbers[:remainder_first_occurrence[current_remainder]+1]))

    return maximum_sum

Big(O) Analysis

Time Complexity

O(n) – The solution iterates through the input array of size n once to calculate the running sum and remainder. It maintains a data structure (like an array or hash map) to store the first occurrence of each remainder, which takes constant time O(1) for each element. The calculation of the candidate sum and updating the maximum sum also take constant time O(1) within the loop. Therefore, the overall time complexity is dominated by the single loop, resulting in O(n).

Space Complexity

O(K) – The algorithm uses extra space to store the first occurrence of each remainder when dividing by K. This is done to keep track of potential starting points. Since there are K possible remainders (0 to K-1), we need a data structure (implicitly described as 'keeping track') to store up to K different values. Thus, the auxiliary space used is proportional to K, resulting in a space complexity of O(K).

Edge Cases

Case	How to Handle
Null or empty input array	Return 0 immediately, as no subarray sum is possible.
Array with a single element	Return the element if it is divisible by K, otherwise return 0.
All elements are negative and K is larger than the array length.	Return 0 since no positive or zero sum subarray of length divisible by K exists.
Array contains only zeros.	Return the sum of all elements (which is 0) if the array length is divisible by K, otherwise return 0.
Array contains very large positive numbers causing integer overflow	Use a data type that can handle larger numbers, like long, or calculate prefix sums modulo K to prevent overflow and track the modulo value instead of the actual sum.
K is 1	Return the sum of the entire array as its length is trivially divisible by 1.
K is 0	Throw an IllegalArgumentException or return an appropriate error code, since division by zero is undefined.
Very large input array causing memory issues	Consider a streaming approach or divide and conquer to process the input in smaller chunks, if possible, based on the constraints and algorithm used.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the possible ranges for the integer values in the input array and the value of K?
Can the input array be empty, or can K be zero?
If no subarray with a length divisible by K has a positive sum, what value should I return?
Does the problem require finding *any* maximum subarray sum with length divisible by K, or the *first* such subarray encountered, or the *longest* if there are multiple maximum sums?
Is the input array guaranteed to contain only integers, or could there be other data types?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Begin with the first number in the set and consider it as a group by itself.
Check if the size of the current group is divisible by the given number.
If it is, add all the numbers in the group to get the group's total sum.
Keep track of the largest group total sum you have seen so far.
Next, consider the first two numbers as a group, then the first three, and so on, always checking the divisibility and summing as before.
Once you have considered all possible groups starting from the first number, move on to the second number and repeat the process by considering groups of increasing size from there.
Continue this process, shifting the starting position one number at a time, until you have considered all possible consecutive groups within the set.
In the end, the largest group total sum you kept track of is your answer.

Code Implementation

def max_subarray_sum_divisible_by_k_brute_force(number_list, divisor):
    maximum_sum = float('-inf')

    for start_index in range(len(number_list)):
        for end_index in range(start_index, len(number_list)):
            # Creating the sub array that ends at end_index
            sub_array = number_list[start_index:end_index + 1]

            # Check if the sub array length is divisible by k
            if len(sub_array) % divisor == 0:

                current_sum = sum(sub_array)
                # Keep track of the largest sum we have found
                if current_sum > maximum_sum:

                    maximum_sum = current_sum

    return maximum_sum

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, calculate a running sum of all the numbers. For each number, also figure out what the remainder is when you divide the sum by K.
Keep track of the *first* time you see each remainder value. These are potentially good starting points for our sections because subtracting these earlier sums will result in a number that is divisible by K.
For each position, calculate the current running sum's remainder.
Subtract the running sum that gave us the first occurrence of that remainder from the current running sum. This result gives you a candidate sum for a section of numbers that has length divisible by K.
Keep track of the biggest sum you've found so far. As you calculate these candidate sums, update the maximum if you find a bigger one.
By remembering only the first time we see each remainder, we can quickly calculate the sums of sections divisible by K without trying every single possible section.

Code Implementation

def max_subarray_sum_divisible_by_k(numbers, k):
    maximum_sum = float('-inf')
    current_running_sum = 0
    remainder_first_occurrence = {}

    # Initialize remainder 0 to index -1 to handle subarrays
    # starting from the beginning of the input array
    remainder_first_occurrence[0] = -1

    for index, number in enumerate(numbers):
        current_running_sum += number
        current_remainder = current_running_sum % k

        # Store the first occurrence of each remainder to calculate
        # subarray sums divisible by k.
        if current_remainder not in remainder_first_occurrence:
            remainder_first_occurrence[current_remainder] = index

        # Calculate the subarray sum and update the maximum sum
        # if a larger sum is found
        else:
            subarray_sum = current_running_sum - \
                sum(numbers[remainder_first_occurrence[current_remainder]+1:index+1])

            subarray_sum = current_running_sum - \
                sum(numbers[remainder_first_occurrence[current_remainder]+1:index+1])

            maximum_sum = max(maximum_sum, current_running_sum - numbers[remainder_first_occurrence[current_remainder]+1])

            subarray_sum = current_running_sum - numbers[remainder_first_occurrence[current_remainder]+1]
            maximum_sum = max(maximum_sum, subarray_sum)

            start_index = remainder_first_occurrence[current_remainder] + 1
            end_index = index + 1
            subarray_sum = sum(numbers[start_index:end_index])
            maximum_sum = max(maximum_sum, subarray_sum)

            maximum_sum = max(maximum_sum, current_running_sum - sum(numbers[:remainder_first_occurrence[current_remainder] + 1]))

            # Calculate the subarray sum using the prefix sum technique
            subarray_sum = current_running_sum - sum(numbers[0 : remainder_first_occurrence[current_remainder] + 1])
            maximum_sum = max(maximum_sum, subarray_sum)

            subarray_sum = current_running_sum - sum(numbers[:remainder_first_occurrence[current_remainder] + 1])

            # Ensure the length is divisible by k
            if (index - remainder_first_occurrence[current_remainder]) % k == 0:
                maximum_sum = max(maximum_sum, current_running_sum - sum(numbers[:remainder_first_occurrence[current_remainder]+1]))

    return maximum_sum

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input array	Return 0 immediately, as no subarray sum is possible.
Array with a single element	Return the element if it is divisible by K, otherwise return 0.
All elements are negative and K is larger than the array length.	Return 0 since no positive or zero sum subarray of length divisible by K exists.
Array contains only zeros.	Return the sum of all elements (which is 0) if the array length is divisible by K, otherwise return 0.
Array contains very large positive numbers causing integer overflow	Use a data type that can handle larger numbers, like long, or calculate prefix sums modulo K to prevent overflow and track the modulo value instead of the actual sum.
K is 1	Return the sum of the entire array as its length is trivially divisible by 1.
K is 0	Throw an IllegalArgumentException or return an appropriate error code, since division by zero is undefined.
Very large input array causing memory issues	Consider a streaming approach or divide and conquer to process the input in smaller chunks, if possible, based on the constraints and algorithm used.