Problem Description

You are given an integer array nums and two integers firstLen and secondLen. Your task is to find two non-overlapping subarrays from nums - one with length firstLen and another with length secondLen - such that the sum of elements in both subarrays is maximized.

Key requirements:

• Both subarrays must be contiguous (elements must be consecutive in the original array)
• The two subarrays cannot overlap (they cannot share any elements)
• The first subarray (with length firstLen) can appear either before or after the second subarray (with length secondLen) in the array
• You need to return the maximum possible sum of elements from both subarrays combined

For example, if nums = [0,6,5,2,2,5,1,9,4], firstLen = 1, and secondLen = 2:

• You could choose subarray [9] (length 1, sum = 9) and subarray [6,5] (length 2, sum = 11)
• The total sum would be 9 + 11 = 20
• This would be the maximum possible sum for two non-overlapping subarrays with the given lengths

The solution uses a sliding window approach with prefix sums to efficiently calculate subarray sums. It considers two scenarios: placing the firstLen subarray before the secondLen subarray, and placing the secondLen subarray before the firstLen subarray. For each position, it tracks the maximum sum of the first subarray seen so far and combines it with the current second subarray to find the overall maximum sum.

Intuition

The key insight is that for two non-overlapping subarrays, one must come before the other. This means we have two possible arrangements:

1. A subarray of length firstLen followed by a subarray of length secondLen
2. A subarray of length secondLen followed by a subarray of length firstLen

To find the maximum sum efficiently, we need to avoid checking all possible pairs of subarrays, which would be O(n²). Instead, we can use a sliding window technique combined with dynamic tracking.

The clever observation is: as we slide through the array looking for the second subarray, we can keep track of the best first subarray we've seen so far. At each position i, we ask:

• "What's the best first subarray that ends before position i?"
• "What's the sum of the second subarray starting at position i?"
• The sum of these two gives us a candidate for our answer

To calculate subarray sums quickly, we use prefix sums. With prefix sum array s, the sum of elements from index i to j is simply s[j+1] - s[i].

The algorithm works in two passes:

1. First pass: Place firstLen subarray first. As we move right, we track the maximum sum of any firstLen subarray seen so far, then check if combining it with the current secondLen subarray gives a better total.

2. Second pass: Place secondLen subarray first. We do the same process but with the roles reversed.

The variable t maintains the running maximum of the first subarray encountered, ensuring we always pair the current second subarray with the best possible first subarray that doesn't overlap with it. This reduces our time complexity from O(n²) to O(n).

Learn more about Dynamic Programming and Sliding Window patterns.

Solution Approach

The implementation uses prefix sums and a two-pass sliding window approach to find the maximum sum of two non-overlapping subarrays.

Step 1: Build Prefix Sum Array

s = list(accumulate(nums, initial=0))

We create a prefix sum array s where s[i] represents the sum of all elements from index 0 to i-1. This allows us to calculate any subarray sum in O(1) time: the sum from index i to j is s[j+1] - s[i].

Step 2: First Pass - firstLen before secondLen

ans = t = 0
i = firstLen
while i + secondLen - 1 < n:
    t = max(t, s[i] - s[i - firstLen])
    ans = max(ans, t + s[i + secondLen] - s[i])
    i += 1

• Start at position i = firstLen (the earliest position where we can place the second subarray)
• t tracks the maximum sum of any firstLen subarray ending at or before position i-1
• At each position i:
  • Update t with the sum of the firstLen subarray ending at position i-1: s[i] - s[i - firstLen]
  • Calculate the sum of the secondLen subarray starting at position i: s[i + secondLen] - s[i]
  • Update ans with the maximum of current answer and t + current_secondLen_sum
• Continue until we can't fit a secondLen subarray anymore

Step 3: Second Pass - secondLen before firstLen

t = 0
i = secondLen
while i + firstLen - 1 < n:
    t = max(t, s[i] - s[i - secondLen])
    ans = max(ans, t + s[i + firstLen] - s[i])
    i += 1

This pass mirrors the first pass but with reversed roles:

• Start at position i = secondLen
• t now tracks the maximum sum of any secondLen subarray ending at or before position i-1
• Calculate the sum of the firstLen subarray starting at position i
• Update the answer accordingly

Why This Works:

• By maintaining the running maximum (t) of the first subarray, we ensure that at each position, we're pairing the current second subarray with the best possible first subarray that doesn't overlap
• The two passes cover both possible arrangements of the subarrays
• Time complexity is O(n) as we make two linear passes through the array
• Space complexity is O(n) for the prefix sum array

The final answer is the maximum sum found across both arrangements.

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Example: nums = [3, 1, 2, 4, 5], firstLen = 2, secondLen = 1

Step 1: Build Prefix Sum Array

• nums = [3, 1, 2, 4, 5]
• s = [0, 3, 4, 6, 10, 15]
  • s[0] = 0 (initial value)
  • s[1] = 0 + 3 = 3
  • s[2] = 3 + 1 = 4
  • s[3] = 4 + 2 = 6
  • s[4] = 6 + 4 = 10
  • s[5] = 10 + 5 = 15

Step 2: First Pass - firstLen (2) before secondLen (1)

Initialize: ans = 0, t = 0, i = 2 (start at firstLen)

• i = 2:

  • Calculate firstLen subarray ending at i-1: [3,1], sum = s[2] - s[0] = 4 - 0 = 4
  • Update t = max(0, 4) = 4
  • Calculate secondLen subarray starting at i: [2], sum = s[3] - s[2] = 6 - 4 = 2
  • Update ans = max(0, 4 + 2) = 6 (subarrays: [3,1] and [2])

• i = 3:

  • Calculate firstLen subarray ending at i-1: [1,2], sum = s[3] - s[1] = 6 - 3 = 3
  • Update t = max(4, 3) = 4 (keep the better firstLen subarray [3,1])
  • Calculate secondLen subarray starting at i: [4], sum = s[4] - s[3] = 10 - 6 = 4
  • Update ans = max(6, 4 + 4) = 8 (subarrays: [3,1] and [4])

• i = 4:

  • Calculate firstLen subarray ending at i-1: [2,4], sum = s[4] - s[2] = 10 - 4 = 6
  • Update t = max(4, 6) = 6
  • Calculate secondLen subarray starting at i: [5], sum = s[5] - s[4] = 15 - 10 = 5
  • Update ans = max(8, 6 + 5) = 11 (subarrays: [2,4] and [5])

Step 3: Second Pass - secondLen (1) before firstLen (2)

Reset: t = 0, i = 1 (start at secondLen)

• i = 1:

  • Calculate secondLen subarray ending at i-1: [3], sum = s[1] - s[0] = 3 - 0 = 3
  • Update t = max(0, 3) = 3
  • Calculate firstLen subarray starting at i: [1,2], sum = s[3] - s[1] = 6 - 3 = 3
  • Update ans = max(11, 3 + 3) = 11 (no improvement)

• i = 2:

  • Calculate secondLen subarray ending at i-1: [1], sum = s[2] - s[1] = 4 - 3 = 1
  • Update t = max(3, 1) = 3 (keep the better secondLen subarray [3])
  • Calculate firstLen subarray starting at i: [2,4], sum = s[4] - s[2] = 10 - 4 = 6
  • Update ans = max(11, 3 + 6) = 11 (no improvement)

• i = 3:

  • Calculate secondLen subarray ending at i-1: [2], sum = s[3] - s[2] = 6 - 4 = 2
  • Update t = max(3, 2) = 3
  • Calculate firstLen subarray starting at i: [4,5], sum = s[5] - s[3] = 15 - 6 = 9
  • Update ans = max(11, 3 + 9) = 12 (subarrays: [3] and [4,5])

Final Answer: 12

The maximum sum is achieved with subarrays [3] (sum = 3) and [4,5] (sum = 9), giving a total of 12.

Solution Implementation

Time and Space Complexity

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

The algorithm consists of:

• Creating the prefix sum array using accumulate: O(n)
• First while loop iterates from firstLen to n - secondLen, which is at most n iterations: O(n)
• Second while loop iterates from secondLen to n - firstLen, which is at most n iterations: O(n)
• Inside each loop, all operations (max comparisons, array access, arithmetic) are O(1)

Total time complexity: O(n) + O(n) + O(n) = O(n)

Space Complexity: O(n)

The algorithm uses:

• Prefix sum array s of size n + 1: O(n)
• A few constant variables (ans, t, i, n): O(1)

Total space complexity: O(n) + O(1) = O(n)

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

Common Pitfalls

1. Off-by-One Errors in Index Calculations

One of the most common mistakes is incorrectly calculating the start and end indices for subarrays, especially when working with prefix sums.

Pitfall Example:

# INCORRECT: Confusing array indices with prefix sum indices
for i in range(firstLen, n):
    first_sum = prefix_sum[i] - prefix_sum[i - firstLen]  # Wrong!
    # This actually gives sum from i-firstLen to i-1, not ending at i

Solution: Always remember that with prefix sums:

• prefix_sum[i] contains the sum of elements from index 0 to i-1
• To get sum from index start to end (inclusive), use: prefix_sum[end + 1] - prefix_sum[start]

2. Not Considering Both Arrangements

A critical mistake is only checking one arrangement (e.g., first array before second array) and forgetting that the arrays can be in either order.

Pitfall Example:

# INCORRECT: Only checking one arrangement
def maxSumTwoNoOverlap(self, nums, firstLen, secondLen):
    # Only considers firstLen array before secondLen array
    for i in range(firstLen, len(nums) - secondLen + 1):
        # ... calculate sums ...
    return result  # Missing half the possible solutions!

Solution: Always check both arrangements:

1. First array of length firstLen before second array of length secondLen
2. Second array of length secondLen before first array of length firstLen

3. Incorrect Loop Boundaries

Setting wrong loop boundaries can cause index out of bounds errors or miss valid subarrays.

Pitfall Example:

# INCORRECT: Loop boundary doesn't ensure enough space for second array
for i in range(firstLen, n):  # Wrong!
    second_sum = prefix_sum[i + secondLen] - prefix_sum[i]  # May go out of bounds

Solution: Ensure your loop boundaries leave enough space for both arrays:

# CORRECT: Ensure there's room for secondLen array after position i
for i in range(firstLen, n - secondLen + 1):
    second_sum = prefix_sum[i + secondLen] - prefix_sum[i]

4. Not Tracking Maximum of Previous Subarrays

A subtle mistake is recalculating the maximum of all previous subarrays at each step instead of maintaining a running maximum.

Pitfall Example:

# INEFFICIENT: Recalculating max every time (O(n²) complexity)
for i in range(firstLen + secondLen, n + 1):
    max_first = 0
    # Recalculating max of all previous firstLen subarrays
    for j in range(0, i - secondLen - firstLen + 1):
        first_sum = prefix_sum[j + firstLen] - prefix_sum[j]
        max_first = max(max_first, first_sum)
    # ... rest of logic

Solution: Maintain a running maximum that gets updated incrementally:

# CORRECT: Maintain running maximum (O(n) complexity)
max_first_sum = 0
for i in range(firstLen + secondLen, n + 1):
    # Only check the new subarray that becomes available
    new_first_sum = prefix_sum[i - secondLen] - prefix_sum[i - secondLen - firstLen]
    max_first_sum = max(max_first_sum, new_first_sum)
    # ... rest of logic

5. Forgetting Edge Cases

Not handling edge cases like when the array length equals firstLen + secondLen.

Solution: Ensure your solution handles:

• Arrays where len(nums) == firstLen + secondLen (only one valid configuration)
• Arrays with negative numbers (prefix sums can decrease)
• Cases where firstLen == secondLen (both arrangements might give the same result, but still need to check both)