Jobs

Interviews

Discussions

Maximum Sum of 3 Non-Overlapping Subarrays

Hard

Asked by:

More companies

65 views

Topics:

ArraysSliding WindowsDynamic Programming

Given an integer array nums and an integer k, find three non-overlapping subarrays of length k with maximum sum and return them.

Return the result as a list of indices representing the starting position of each interval (0-indexed). If there are multiple answers, return the lexicographically smallest one.

Example 1:

Input: nums = [1,2,1,2,6,7,5,1], k = 2
Output: [0,3,5]
Explanation: Subarrays [1, 2], [2, 6], [7, 5] correspond to the starting indices [0, 3, 5].
We could have also taken [2, 1], but an answer of [1, 3, 5] would be lexicographically larger.

Example 2:

Input: nums = [1,2,1,2,1,2,1,2,1], k = 2
Output: [0,2,4]

Constraints:

1 <= nums.length <= 2 * 10⁴
1 <= nums[i] < 2¹⁶
1 <= k <= floor(nums.length / 3)

Try coding it in LeetCode

Maximum Sum of 3 Non-Overlapping Subarrays

Hard

Asked by:

65 views

Topics:

ArraysSliding WindowsDynamic Programming

Given an integer array nums and an integer k, find three non-overlapping subarrays of length k with maximum sum and return them.

Return the result as a list of indices representing the starting position of each interval (0-indexed). If there are multiple answers, return the lexicographically smallest one.

Example 1:

Input: nums = [1,2,1,2,6,7,5,1], k = 2
Output: [0,3,5]
Explanation: Subarrays [1, 2], [2, 6], [7, 5] correspond to the starting indices [0, 3, 5].
We could have also taken [2, 1], but an answer of [1, 3, 5] would be lexicographically larger.

Example 2:

Input: nums = [1,2,1,2,1,2,1,2,1], k = 2
Output: [0,2,4]

Constraints:

1 <= nums.length <= 2 * 10⁴
1 <= nums[i] < 2¹⁶
1 <= k <= floor(nums.length / 3)

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 constraints on the values within the input array and the length of the array? Can I assume the values are integers and are there any limits on their range (positive, negative, zero)?
Is 'k' always guaranteed to be a valid size such that 3 * k <= length of the input array? What should I return if 3 * k exceeds the array length?
If multiple sets of three non-overlapping subarrays result in the maximum sum, is there a specific criteria for choosing one (e.g., lexicographically smallest indices)?
Should I return the starting indices of the subarrays or the subarrays themselves? Can you provide an example of the expected output format?
Can the value of k be zero?

Brute Force Solution

Approach

The brute force method for this problem is all about trying every single combination of three non-overlapping groups and picking the best one. We check the sum of all the groups and see which combination gives us the largest possible sum.

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

First, imagine dividing the collection of numbers into three separate sections.
Start by considering the very first possible section of a specific length. Calculate the sum of the numbers in this section.
Next, slide this first section along a little bit, one number at a time, creating many slightly different first sections. Calculate the sum for each of these.
For each of these first sections, consider all possible second sections that don't overlap with the first, again calculating the sum of each possible second section.
For each combination of first and second sections, find the largest possible third section that doesn't overlap with the previous two, and calculate its sum.
Add up the sums of the three sections for each combination.
Keep track of which combination of three sections gives you the biggest total sum.
After checking all possible combinations of first, second, and third sections, the one with the highest total sum is your answer.

Code Implementation

def max_sum_three_subarrays_brute_force(numbers, subarray_length):
    max_sum = 0
    best_indices = []
    list_length = len(numbers)

    # Iterate through all possible starting positions for the first subarray
    for first_subarray_start in range(list_length - (3 * subarray_length) + 1):

        first_subarray_sum = sum(numbers[first_subarray_start:first_subarray_start + subarray_length])

        # Iterate through all possible starting positions for the second subarray
        for second_subarray_start in range(first_subarray_start + subarray_length, list_length - (2 * subarray_length) + 1):

            second_subarray_sum = sum(numbers[second_subarray_start:second_subarray_start + subarray_length])

            # Find the largest possible third section that doesn't overlap with the previous two
            for third_subarray_start in range(second_subarray_start + subarray_length, list_length - subarray_length + 1):

                third_subarray_sum = sum(numbers[third_subarray_start:third_subarray_start + subarray_length])

                current_sum = first_subarray_sum + second_subarray_sum + third_subarray_sum

                # Keep track of which combination gives you the biggest total sum
                if current_sum > max_sum:
                    max_sum = current_sum
                    best_indices = [first_subarray_start, second_subarray_start, third_subarray_start]

    return best_indices

Big(O) Analysis

Time Complexity

O(n^3) – The brute force approach iterates through all possible starting positions for the first subarray. For each of these positions, it then iterates through all possible starting positions for the second subarray that do not overlap the first. Finally, for each combination of the first and second subarrays, it iterates through all possible starting positions for the third subarray that do not overlap the previous two. Since each of these three loops iterates through a number of positions proportional to n (the size of the input array), the total number of operations is proportional to n * n * n. Therefore, the time complexity is O(n^3).

Space Complexity

O(1) – The brute force approach, as described, primarily involves iterating and calculating sums without storing significant amounts of data beyond a few variables. It keeps track of the maximum sum found so far and the corresponding indices, using constant space. The size of the input array, N, does not affect the amount of extra memory allocated for these variables. Therefore, the space complexity remains constant, independent of the input size.

Optimal Solution

Approach

The best way to find the maximum sum of three non-overlapping subarrays is to cleverly precompute some sums and then efficiently check the possible starting positions. We avoid checking every single combination by reusing calculations and focusing on promising spots. This saves a huge amount of time.

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

First, calculate the sum of every possible subarray of the given length. Store these sums so you can quickly look them up later instead of recalculating them repeatedly.
Then, for each possible 'middle' subarray, find the best (highest sum) subarray that comes *before* it and the best subarray that comes *after* it. Remember, these subarrays can't overlap.
To find the best 'before' and 'after' subarrays efficiently, go through the precomputed sums from left to right to find the best 'before', and from right to left to find the best 'after'. Keep track of the best ones as you go. This way, you don't have to re-scan everything for each middle subarray.
Finally, loop through all possible middle subarrays, and for each one, combine its sum with the sum of its best 'before' subarray and its best 'after' subarray. Keep track of the largest total sum you find. Also keep track of the starting positions for the best 'before', 'middle', and 'after' subarrays that give you that maximum sum.
The starting positions you've kept track of will give you the locations of the three non-overlapping subarrays with the largest possible combined sum.

Code Implementation

def max_sum_three_subarrays(numbers, subarray_length):
    number_of_elements = len(numbers)
    if number_of_of_elements < 3 * subarray_length:
        return []

    # Calculate the sums of all possible subarrays of length k.
    subarray_sums = []
    current_sum = sum(numbers[:subarray_length])
    subarray_sums.append(current_sum)

    for i in range(subarray_length, number_of_elements):
        current_sum = current_sum - numbers[i - subarray_length] + numbers[i]
        subarray_sums.append(current_sum)

    # left_indices[i] is the index of the best subarray ending at i
    left_indices = [0] * len(subarray_sums)
    best_index = 0
    for i in range(len(subarray_sums)): 
        if subarray_sums[i] > subarray_sums[best_index]:
            best_index = i
        left_indices[i] = best_index

    # right_indices[i] is the index of the best subarray starting at i
    right_indices = [0] * len(subarray_sums)
    best_index = len(subarray_sums) - 1

    for i in range(len(subarray_sums) - 1, -1, -1):
        if subarray_sums[i] >= subarray_sums[best_index]:
            best_index = i
        right_indices[i] = best_index

    # Find the three non-overlapping subarrays with maximum sum.
    max_total_sum = 0
    result_indices = []

    # Iterate through possible middle subarray start positions.
    for j in range(subarray_length, len(subarray_sums) - subarray_length):
        left_index = left_indices[j - subarray_length]
        right_index = right_indices[j + subarray_length]
        current_total_sum = subarray_sums[left_index] + subarray_sums[j] + subarray_sums[right_index]

        # Update result if current combination is better.
        if current_total_sum > max_total_sum:
            max_total_sum = current_total_sum

            # Store the start indices to return.
            result_indices = [left_index, j, right_index]

    # Adjust to return start indices of original array.
    return [index for index in result_indices]

Big(O) Analysis

Time Complexity

O(n) – The algorithm first calculates the sum of all subarrays of size k, which takes O(n) time. It then finds the best 'before' subarrays in O(n) time by iterating from left to right, and the best 'after' subarrays in O(n) time by iterating from right to left. Finally, it iterates through all possible middle subarrays (again, O(n)), combining their sums with the precomputed best 'before' and 'after' sums. Therefore, the dominant operation involves a single loop through the array of size n, resulting in a time complexity of O(n).

Space Complexity

O(N) – The algorithm precomputes and stores the sum of every possible subarray of length k in an array of size N-k+1, where N is the length of the input array. It also maintains two additional arrays of size N-k+1 to store the best 'before' and 'after' subarray sums. Therefore, the auxiliary space used scales linearly with the input size N, resulting in a space complexity of O(N).

Edge Cases

Case	How to Handle
Empty input array	Return an empty list or null, as there are no subarrays to sum.
Array size less than 3*k (where k is the subarray size)	Return an empty list or null, because three non-overlapping subarrays of size k cannot exist.
k is greater than array size / 3	Return an empty list or null as valid 3 subarrays can not be formed.
Large input array size impacting performance	The solution should have a time complexity of O(n) to handle large input arrays efficiently.
Array contains all negative numbers	The algorithm should correctly identify the three subarrays with the least negative sum, maximizing the overall sum.
Array contains all zero values	The algorithm should return the starting indices of the first three subarrays of size k.
Integer overflow when calculating sums for large numbers or k	Use long data type to store intermediate sums to prevent integer overflow.
Multiple sets of subarrays with the same maximum sum	The algorithm should return the lexicographically smallest starting indices of the three subarrays.

Empty input array

How to Handle:

Return an empty list or null, as there are no subarrays to sum.

Array size less than 3*k (where k is the subarray size)

How to Handle:

Return an empty list or null, because three non-overlapping subarrays of size k cannot exist.

k is greater than array size / 3

How to Handle:

Return an empty list or null as valid 3 subarrays can not be formed.

Large input array size impacting performance

How to Handle:

The solution should have a time complexity of O(n) to handle large input arrays efficiently.

Array contains all negative numbers

How to Handle:

The algorithm should correctly identify the three subarrays with the least negative sum, maximizing the overall sum.

Array contains all zero values

How to Handle:

The algorithm should return the starting indices of the first three subarrays of size k.

Integer overflow when calculating sums for large numbers or k

How to Handle:

Use long data type to store intermediate sums to prevent integer overflow.

Multiple sets of subarrays with the same maximum sum

How to Handle:

The algorithm should return the lexicographically smallest starting indices of the three subarrays.

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 constraints on the values within the input array and the length of the array? Can I assume the values are integers and are there any limits on their range (positive, negative, zero)?
Is 'k' always guaranteed to be a valid size such that 3 * k <= length of the input array? What should I return if 3 * k exceeds the array length?
If multiple sets of three non-overlapping subarrays result in the maximum sum, is there a specific criteria for choosing one (e.g., lexicographically smallest indices)?
Should I return the starting indices of the subarrays or the subarrays themselves? Can you provide an example of the expected output format?
Can the value of k be zero?

Brute Force Solution

Approach

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

First, imagine dividing the collection of numbers into three separate sections.
Start by considering the very first possible section of a specific length. Calculate the sum of the numbers in this section.
Next, slide this first section along a little bit, one number at a time, creating many slightly different first sections. Calculate the sum for each of these.
For each of these first sections, consider all possible second sections that don't overlap with the first, again calculating the sum of each possible second section.
For each combination of first and second sections, find the largest possible third section that doesn't overlap with the previous two, and calculate its sum.
Add up the sums of the three sections for each combination.
Keep track of which combination of three sections gives you the biggest total sum.
After checking all possible combinations of first, second, and third sections, the one with the highest total sum is your answer.

Code Implementation

def max_sum_three_subarrays_brute_force(numbers, subarray_length):
    max_sum = 0
    best_indices = []
    list_length = len(numbers)

    # Iterate through all possible starting positions for the first subarray
    for first_subarray_start in range(list_length - (3 * subarray_length) + 1):

        first_subarray_sum = sum(numbers[first_subarray_start:first_subarray_start + subarray_length])

        # Iterate through all possible starting positions for the second subarray
        for second_subarray_start in range(first_subarray_start + subarray_length, list_length - (2 * subarray_length) + 1):

            second_subarray_sum = sum(numbers[second_subarray_start:second_subarray_start + subarray_length])

            # Find the largest possible third section that doesn't overlap with the previous two
            for third_subarray_start in range(second_subarray_start + subarray_length, list_length - subarray_length + 1):

                third_subarray_sum = sum(numbers[third_subarray_start:third_subarray_start + subarray_length])

                current_sum = first_subarray_sum + second_subarray_sum + third_subarray_sum

                # Keep track of which combination gives you the biggest total sum
                if current_sum > max_sum:
                    max_sum = current_sum
                    best_indices = [first_subarray_start, second_subarray_start, third_subarray_start]

    return best_indices

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

First, calculate the sum of every possible subarray of the given length. Store these sums so you can quickly look them up later instead of recalculating them repeatedly.
Then, for each possible 'middle' subarray, find the best (highest sum) subarray that comes *before* it and the best subarray that comes *after* it. Remember, these subarrays can't overlap.
To find the best 'before' and 'after' subarrays efficiently, go through the precomputed sums from left to right to find the best 'before', and from right to left to find the best 'after'. Keep track of the best ones as you go. This way, you don't have to re-scan everything for each middle subarray.
Finally, loop through all possible middle subarrays, and for each one, combine its sum with the sum of its best 'before' subarray and its best 'after' subarray. Keep track of the largest total sum you find. Also keep track of the starting positions for the best 'before', 'middle', and 'after' subarrays that give you that maximum sum.
The starting positions you've kept track of will give you the locations of the three non-overlapping subarrays with the largest possible combined sum.

Code Implementation

def max_sum_three_subarrays(numbers, subarray_length):
    number_of_elements = len(numbers)
    if number_of_of_elements < 3 * subarray_length:
        return []

    # Calculate the sums of all possible subarrays of length k.
    subarray_sums = []
    current_sum = sum(numbers[:subarray_length])
    subarray_sums.append(current_sum)

    for i in range(subarray_length, number_of_elements):
        current_sum = current_sum - numbers[i - subarray_length] + numbers[i]
        subarray_sums.append(current_sum)

    # left_indices[i] is the index of the best subarray ending at i
    left_indices = [0] * len(subarray_sums)
    best_index = 0
    for i in range(len(subarray_sums)): 
        if subarray_sums[i] > subarray_sums[best_index]:
            best_index = i
        left_indices[i] = best_index

    # right_indices[i] is the index of the best subarray starting at i
    right_indices = [0] * len(subarray_sums)
    best_index = len(subarray_sums) - 1

    for i in range(len(subarray_sums) - 1, -1, -1):
        if subarray_sums[i] >= subarray_sums[best_index]:
            best_index = i
        right_indices[i] = best_index

    # Find the three non-overlapping subarrays with maximum sum.
    max_total_sum = 0
    result_indices = []

    # Iterate through possible middle subarray start positions.
    for j in range(subarray_length, len(subarray_sums) - subarray_length):
        left_index = left_indices[j - subarray_length]
        right_index = right_indices[j + subarray_length]
        current_total_sum = subarray_sums[left_index] + subarray_sums[j] + subarray_sums[right_index]

        # Update result if current combination is better.
        if current_total_sum > max_total_sum:
            max_total_sum = current_total_sum

            # Store the start indices to return.
            result_indices = [left_index, j, right_index]

    # Adjust to return start indices of original array.
    return [index for index in result_indices]

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty input array	Return an empty list or null, as there are no subarrays to sum.
Array size less than 3*k (where k is the subarray size)	Return an empty list or null, because three non-overlapping subarrays of size k cannot exist.
k is greater than array size / 3	Return an empty list or null as valid 3 subarrays can not be formed.
Large input array size impacting performance	The solution should have a time complexity of O(n) to handle large input arrays efficiently.
Array contains all negative numbers	The algorithm should correctly identify the three subarrays with the least negative sum, maximizing the overall sum.
Array contains all zero values	The algorithm should return the starting indices of the first three subarrays of size k.
Integer overflow when calculating sums for large numbers or k	Use long data type to store intermediate sums to prevent integer overflow.
Multiple sets of subarrays with the same maximum sum	The algorithm should return the lexicographically smallest starting indices of the three subarrays.

Empty input array

How to Handle:

Return an empty list or null, as there are no subarrays to sum.

Array size less than 3*k (where k is the subarray size)

How to Handle:

Return an empty list or null, because three non-overlapping subarrays of size k cannot exist.

k is greater than array size / 3

How to Handle:

Return an empty list or null as valid 3 subarrays can not be formed.

Large input array size impacting performance

How to Handle:

The solution should have a time complexity of O(n) to handle large input arrays efficiently.

Array contains all negative numbers

How to Handle:

The algorithm should correctly identify the three subarrays with the least negative sum, maximizing the overall sum.

Array contains all zero values

How to Handle:

The algorithm should return the starting indices of the first three subarrays of size k.

Integer overflow when calculating sums for large numbers or k

How to Handle:

Use long data type to store intermediate sums to prevent integer overflow.

Multiple sets of subarrays with the same maximum sum

How to Handle:

The algorithm should return the lexicographically smallest starting indices of the three subarrays.