LeetCode 689 - Maximum Sum of 3 Non-Overlapping Subarrays

LeetCode Problem 689

Difficulty: 🔴 Hard
Topics: Array, Dynamic Programming, Sliding Window, Prefix Sum

Solution

Problem Understanding

The problem asks us to select exactly three non-overlapping subarrays from the input array nums, where each subarray has length k. Among all valid choices, we must maximize the total sum of all elements contained in those three subarrays.

The output is not the subarrays themselves, but the starting indices of those three subarrays. Since the intervals must not overlap, if one subarray starts at index i, then the next valid subarray must start at index at least i + k.

The lexicographical ordering requirement is extremely important. If multiple solutions produce the same maximum total sum, we must return the one with the smallest indices when compared from left to right. For example, [0,3,5] is lexicographically smaller than [1,3,5] because the first differing index is smaller.

The input constraints are large enough that brute force enumeration becomes impractical. The array length can be as large as 2 * 10^4, which means any cubic or even quadratic-heavy solution will struggle. This strongly suggests that we need a linear or near-linear algorithm.

Several details are important:

• Every subarray has exactly length k
• We must choose exactly three subarrays
• The chosen subarrays cannot overlap
• Multiple optimal answers may exist, and we must return the lexicographically smallest one
• The constraints guarantee that at least three subarrays can exist because k <= floor(nums.length / 3)

A naive implementation can easily fail in tie-breaking scenarios. Another common bug is accidentally allowing overlapping intervals when computing the best combinations independently.

Approaches

Brute Force Approach

The most straightforward solution is to enumerate every possible combination of three subarrays.

First, we compute the sum of every window of size k. If there are m = n - k + 1 possible windows, we can try all triples (i, j, l) such that:

• i + k <= j
• j + k <= l

For every valid triple, we compute:

windowSum[i] + windowSum[j] + windowSum[l]

We track the maximum total and update the answer whenever we find a better combination.

This approach is correct because it exhaustively checks every valid possibility. However, it is far too slow. There can be roughly O(n) possible starting positions for each subarray, leading to an O(n^3) search space.

With n = 2 * 10^4, cubic complexity is infeasible.

Key Insight for the Optimal Solution

The critical observation is that once we fix the middle subarray, the left and right choices become independent optimization problems.

Suppose the middle subarray starts at index mid.

Then:

• The left subarray must end before mid
• The right subarray must begin after mid + k - 1

For every possible middle position, we want:

• The best left window before it
• The best right window after it

If we precompute these efficiently, then every middle position can be evaluated in constant time.

This transforms the problem from trying all triples into:

• Precompute all window sums
• Precompute the best left index for every position
• Precompute the best right index for every position
• Iterate through possible middle windows

This reduces the complexity to linear time.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n³)	O(n)	Enumerates all valid triples of subarrays
Optimal	O(n)	O(n)	Uses sliding window and precomputed best left/right intervals

Algorithm Walkthrough

Step 1: Compute All Window Sums

First, compute the sum of every subarray of length k.

We use a sliding window because recalculating each sum independently would be inefficient.

If:

nums = [1,2,1,2,6,7,5,1]
k = 2

Then the window sums become:

[3,3,3,8,13,12,6]

Each entry represents the sum of a size-k subarray starting at that index.

Step 2: Build the Best Left Array

We create an array called bestLeft.

For every position i, bestLeft[i] stores the index of the maximum-sum window in the range [0, i].

If multiple windows have the same sum, we keep the earlier index to preserve lexicographical ordering.

Example:

windowSums = [3,3,3,8,13,12,6]
bestLeft   = [0,0,0,3,4,4,4]

At position 5, the best window seen so far starts at index 4 because sum 13 is largest.

Step 3: Build the Best Right Array

Now create bestRight.

For every position i, bestRight[i] stores the index of the maximum-sum window in the range [i, end].

This array is built from right to left.

Tie-breaking is subtle here. We use >= instead of > so that earlier indices are preferred during ties.

Example:

bestRight = [4,4,4,4,4,5,6]

Step 4: Enumerate the Middle Window

Now iterate through every valid middle window.

If the middle starts at mid:

• Left candidate is bestLeft[mid - k]
• Right candidate is bestRight[mid + k]

This guarantees non-overlap.

The total becomes:

windowSums[left] + windowSums[mid] + windowSums[right]

Track the maximum total and update the answer when necessary.

Step 5: Return the Best Triple

Because of our tie-breaking rules in bestLeft and bestRight, the first optimal solution encountered is automatically lexicographically smallest.

Why it works

The algorithm works because every valid solution can be uniquely represented by its middle interval. Once the middle interval is fixed, the optimal left and right intervals become independent subproblems.

bestLeft guarantees that we always choose the highest-sum valid left interval. bestRight guarantees the same for the right interval. Therefore, every middle position is paired with the best possible surrounding intervals.

Since we evaluate all valid middle intervals, the global optimum must be found.

Python Solution

from typing import List

class Solution:
    def maxSumOfThreeSubarrays(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)

        # Compute all window sums
        window_sums = []
        current_sum = sum(nums[:k])
        window_sums.append(current_sum)

        for i in range(k, n):
            current_sum += nums[i]
            current_sum -= nums[i - k]
            window_sums.append(current_sum)

        m = len(window_sums)

        # best_left[i] = index of best window in [0..i]
        best_left = [0] * m
        best_index = 0

        for i in range(m):
            if window_sums[i] > window_sums[best_index]:
                best_index = i
            best_left[i] = best_index

        # best_right[i] = index of best window in [i..m-1]
        best_right = [0] * m
        best_index = m - 1

        for i in range(m - 1, -1, -1):
            if window_sums[i] >= window_sums[best_index]:
                best_index = i
            best_right[i] = best_index

        max_total = 0
        answer = []

        # Enumerate middle window
        for mid in range(k, m - k):
            left = best_left[mid - k]
            right = best_right[mid + k]

            total = (
                window_sums[left]
                + window_sums[mid]
                + window_sums[right]
            )

            if total > max_total:
                max_total = total
                answer = [left, mid, right]

        return answer

The implementation begins by computing all fixed-length window sums using a sliding window. This converts the original problem into selecting three indices from the window_sums array.

Next, best_left is constructed by scanning from left to right. At every position, it stores the index of the largest window sum encountered so far. Since we only update on strictly greater sums, earlier indices are preserved during ties.

The best_right array is built similarly but from right to left. Here we use >= so that earlier indices win tie-breaks when scanning backward.

Finally, we iterate through every possible middle interval. For each middle index, we instantly retrieve the optimal non-overlapping left and right intervals using the precomputed arrays. This avoids nested searching and reduces the complexity to linear time.

Go Solution

func maxSumOfThreeSubarrays(nums []int, k int) []int {
	n := len(nums)

	// Compute window sums
	windowSums := []int{}
	currentSum := 0

	for i := 0; i < k; i++ {
		currentSum += nums[i]
	}

	windowSums = append(windowSums, currentSum)

	for i := k; i < n; i++ {
		currentSum += nums[i]
		currentSum -= nums[i-k]
		windowSums = append(windowSums, currentSum)
	}

	m := len(windowSums)

	// bestLeft[i] = best window index in [0..i]
	bestLeft := make([]int, m)
	bestIndex := 0

	for i := 0; i < m; i++ {
		if windowSums[i] > windowSums[bestIndex] {
			bestIndex = i
		}
		bestLeft[i] = bestIndex
	}

	// bestRight[i] = best window index in [i..m-1]
	bestRight := make([]int, m)
	bestIndex = m - 1

	for i := m - 1; i >= 0; i-- {
		if windowSums[i] >= windowSums[bestIndex] {
			bestIndex = i
		}
		bestRight[i] = bestIndex
	}

	maxTotal := 0
	answer := []int{}

	// Enumerate middle window
	for mid := k; mid < m-k; mid++ {
		left := bestLeft[mid-k]
		right := bestRight[mid+k]

		total := windowSums[left] +
			windowSums[mid] +
			windowSums[right]

		if total > maxTotal {
			maxTotal = total
			answer = []int{left, mid, right}
		}
	}

	return answer
}

The Go implementation closely mirrors the Python version. Slices are used instead of Python lists, and explicit initialization is required with make.

Integer overflow is not a concern because the constraints keep sums comfortably within Go's int range.

One subtle detail is preserving lexicographical ordering. The same tie-breaking logic is used:

• > for bestLeft
• >= for bestRight

This guarantees the lexicographically smallest optimal answer.

Worked Examples

Example 1

Input:

nums = [1,2,1,2,6,7,5,1]
k = 2

Step 1: Window Sums

Start Index	Subarray	Sum
0	[1,2]	3
1	[2,1]	3
2	[1,2]	3
3	[2,6]	8
4	[6,7]	13
5	[7,5]	12
6	[5,1]	6

windowSums = [3,3,3,8,13,12,6]

Step 2: Build bestLeft

i	Best Window So Far	bestLeft[i]
0	0	0
1	0	0
2	0	0
3	3	3
4	4	4
5	4	4
6	4	4

Step 3: Build bestRight

i	Best Window From Right	bestRight[i]
6	6	6
5	5	5
4	4	4
3	4	4
2	4	4
1	4	4
0	4	4

Step 4: Evaluate Middle Windows

Mid	Left	Right	Total
2	0	4	19
3	0	5	23
4	0	6	22

Best result:

[0,3,5]

Example 2

Input:

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

Window Sums

[3,3,3,3,3,3,3,3]

All windows have identical sums.

Because the algorithm preserves earlier indices during ties:

• bestLeft always prefers smaller indices
• bestRight also resolves ties lexicographically

The result becomes:

[0,2,4]

which is the lexicographically smallest valid answer.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each array is processed a constant number of times
Space	O(n)	Additional arrays store window sums and best indices

The algorithm performs several linear passes:

• One pass to compute window sums
• One pass for bestLeft
• One pass for bestRight
• One pass to evaluate middle intervals

Since all operations inside each pass are constant time, the overall runtime is linear.

The extra space comes from storing:

• window_sums
• best_left
• best_right

Each has size proportional to n.

Test Cases

from typing import List

class Solution:
    def maxSumOfThreeSubarrays(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)

        window_sums = []
        current_sum = sum(nums[:k])
        window_sums.append(current_sum)

        for i in range(k, n):
            current_sum += nums[i]
            current_sum -= nums[i - k]
            window_sums.append(current_sum)

        m = len(window_sums)

        best_left = [0] * m
        best_index = 0

        for i in range(m):
            if window_sums[i] > window_sums[best_index]:
                best_index = i
            best_left[i] = best_index

        best_right = [0] * m
        best_index = m - 1

        for i in range(m - 1, -1, -1):
            if window_sums[i] >= window_sums[best_index]:
                best_index = i
            best_right[i] = best_index

        max_total = 0
        answer = []

        for mid in range(k, m - k):
            left = best_left[mid - k]
            right = best_right[mid + k]

            total = (
                window_sums[left]
                + window_sums[mid]
                + window_sums[right]
            )

            if total > max_total:
                max_total = total
                answer = [left, mid, right]

        return answer

sol = Solution()

assert sol.maxSumOfThreeSubarrays(
    [1,2,1,2,6,7,5,1], 2
) == [0,3,5]  # provided example

assert sol.maxSumOfThreeSubarrays(
    [1,2,1,2,1,2,1,2,1], 2
) == [0,2,4]  # tie-breaking lexicographically

assert sol.maxSumOfThreeSubarrays(
    [1,1,1,1,1,1], 1
) == [0,1,2]  # smallest possible windows

assert sol.maxSumOfThreeSubarrays(
    [9,8,7,6,5,4,3,2,1], 2
) == [0,2,4]  # decreasing values

assert sol.maxSumOfThreeSubarrays(
    [1,2,3,4,5,6,7,8,9], 2
) == [3,5,7]  # increasing values

assert sol.maxSumOfThreeSubarrays(
    [4,5,10,6,11,17,4,5,6,1], 1
) == [2,4,5]  # k = 1

assert sol.maxSumOfThreeSubarrays(
    [5,5,5,5,5,5,5,5,5], 3
) == [0,3,6]  # all windows equal

assert sol.maxSumOfThreeSubarrays(
    [100,1,1,100,1,1,100], 1
) == [0,3,6]  # separated peaks

assert sol.maxSumOfThreeSubarrays(
    [1,2,3,1,2,3,1,2,3], 2
) == [0,3,6]  # repeated patterns

Test Summary

Test	Why
[1,2,1,2,6,7,5,1], k=2	Validates the official example
[1,2,1,2,1,2,1,2,1], k=2	Verifies lexicographical tie-breaking
[1,1,1,1,1,1], k=1	Tests minimum window size
Decreasing sequence	Ensures optimal windows are found early
Increasing sequence	Ensures optimal windows are found late
k=1 case	Simplifies windows into individual elements
All equal values	Tests tie-handling correctness
Distinct peaks	Ensures separated maxima are chosen
Repeated patterns	Tests multiple equivalent structures

Edge Cases

All Window Sums Are Equal

When every window has the same sum, many solutions are equally optimal. A careless implementation might return arbitrary indices depending on traversal order.

This implementation handles the situation correctly by carefully choosing tie-breaking conditions:

• bestLeft only updates on strictly greater sums
• bestRight updates on greater-than-or-equal sums while scanning backward

Together, these rules ensure the lexicographically smallest solution is returned.

Smallest Possible Window Size

When k = 1, every element becomes its own subarray. The problem reduces to selecting three individual elements with maximum total value.

Some implementations accidentally assume windows contain multiple elements and may introduce off-by-one errors. This solution works naturally because the sliding window logic still applies correctly for size 1.

Maximum Overlap Risk

A common bug is accidentally selecting overlapping windows when combining independently optimized intervals.

For example, if the middle interval starts at mid, then:

• Left must come from indices up to mid - k
• Right must come from indices starting at mid + k

This implementation enforces those boundaries explicitly, guaranteeing that no overlap can occur.