Maximum Sum of 3 Non-Overlapping Subarrays: Left-Middle-Right Scan

Given an integer array nums and an integer k, you need to find three non-overlapping subarrays of length k with the maximum total sum. Return the starting indices of those three subarrays. If there are multiple answers, return the lexicographically smallest one.

This is LeetCode 689: Maximum Sum of 3 Non-Overlapping Subarrays, a hard problem that combines prefix sums with a left-right decomposition. The trick is to fix the middle subarray and look up the best left and right subarrays in O(1), giving you an O(n) solution overall.

The approach: prefix sums with left and right best

The brute force way would be to try all triples of non-overlapping starting indices. With three nested loops, that runs in O(n^3) time, which is far too slow for arrays up to length 20,000.

Instead, you can solve this in four clean passes:

1. Compute prefix sums so that any subarray sum of length k can be retrieved in O(1). The sum of nums[i..i+k-1] is simply prefix[i+k] - prefix[i].

2. Build left[i], an array where left[i] stores the starting index of the best (highest-sum) subarray of length k that starts at or before index i. You fill this with a single left-to-right scan. At each position, if the current window beats the previous best, you update.

3. Build right[i], an array where right[i] stores the starting index of the best subarray of length k that starts at or after index i. You fill this with a single right-to-left scan. The key detail: use >= (not >) when comparing sums during the backward scan, so that ties are broken in favor of the smaller (earlier) index.

4. Iterate over all valid middle subarray positions. For each middle start mid, combine left[mid - 1] (the best left subarray that ends before the middle starts) with window_sum(mid) and right[mid + k] (the best right subarray that starts after the middle ends). Track the triple that gives the largest total.

Because each pass is O(n), the entire algorithm runs in O(n) time and O(n) space.

def maxSumOfThreeSubarrays(nums: list[int], k: int) -> list[int]:
    n = len(nums)
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i + 1] = prefix[i] + nums[i]

    def window_sum(i):
        return prefix[i + k] - prefix[i]

    left = [0] * n
    best = 0
    for i in range(k - 1, n):
        if window_sum(i - k + 1) > window_sum(best):
            best = i - k + 1
        left[i] = best

    right = [0] * n
    best = n - k
    for i in range(n - k, -1, -1):
        if window_sum(i) >= window_sum(best):
            best = i
        right[i] = best

    result = []
    max_total = 0
    for mid in range(k, n - 2 * k + 1):
        l = left[mid - 1]
        r = right[mid + k]
        total = window_sum(l) + window_sum(mid) + window_sum(r)
        if total > max_total:
            max_total = total
            result = [l, mid, r]
    return result

Step-by-step walkthrough

Let's trace through the example nums = [1, 2, 1, 2, 6, 7, 5, 1] with k = 2.

Complexity analysis

Time: O(n). You make four linear passes: one for prefix sums, one for the left-best array, one for the right-best array, and one for the middle scan. Each pass visits every element at most once.

Space: O(n). The prefix sum array, the left-best array, and the right-best array each use O(n) space. You could reduce this slightly by computing window sums on the fly, but the asymptotic complexity stays the same.

The building blocks

Prefix sums for range queries

The prefix sum pattern lets you answer "what is the sum of elements from index i to index j?" in O(1) after an O(n) precomputation step. You build an array where prefix[0] = 0 and prefix[i] = prefix[i-1] + nums[i-1]. Then the sum of any subarray nums[i..j] is prefix[j+1] - prefix[i].

This pattern appears everywhere: range sum queries, sliding window problems, and any time you need to compare subarray sums efficiently. Once you have prefix sums, you never need to re-sum a subarray from scratch.

Left-best and right-best arrays

The left-right decomposition is a powerful technique for problems where you need to split an array into segments and optimize each segment independently. The idea is: precompute the best answer to the left of every index, precompute the best answer to the right of every index, then combine them.

In this problem, the "best answer to the left" is the starting index of the highest-sum subarray of length k ending at or before a given position. The "best answer to the right" is the same concept, but looking forward. By precomputing both arrays, the final middle scan can look up the optimal left and right partners in O(1).

This same decomposition shows up in problems like Best Time to Buy and Sell Stock III (precompute best first transaction to the left, best second transaction to the right) and trapping rain water (precompute max height to the left and right of each bar).

Edge cases

Before submitting, make sure your solution handles these scenarios:

• k equals 1. Each subarray is a single element. The algorithm still works, but the windows are trivially one element wide. Make sure your index math does not go out of bounds.

• Exactly 3k elements. There is only one possible triple: indices [0, k, 2k]. The middle scan has exactly one iteration, and the left-best and right-best arrays each point to the only valid option.

• All elements are equal. Every window has the same sum. The algorithm should return [0, k, 2k] because of the lexicographic tie-breaking. The >= in the right-best scan and > in the left-best scan ensure that the smallest indices win.

• Array with a single dominant peak. If one region has much larger values, two of the three subarrays may end up adjacent to each other. The non-overlapping constraint is enforced by the index ranges: left[mid - 1] guarantees the left subarray ends before mid, and right[mid + k] guarantees the right subarray starts after the middle ends.

• Negative numbers are absent. The problem guarantees nums[i] >= 1, so every window sum is positive. You do not need to handle negative sums or empty-subarray edge cases.

From understanding to recall

Reading through this solution once gives you the idea, but reproducing it from memory is a different challenge. Can you remember the four passes? Do you recall which scan uses > and which uses >=? Can you set up the middle scan boundaries correctly without checking a reference?

Spaced repetition bridges that gap. You revisit the prefix sum setup, the left-right decomposition, and the middle scan at increasing intervals. Each time you rebuild the solution from scratch. After a few cycles, the pattern becomes automatic, and you can apply it to new problems that use the same left-right decomposition structure.

The prefix sum pattern and the left-right best decomposition are two of roughly 60 reusable building blocks that appear across hundreds of LeetCode problems. Learning each one individually and reinforcing it with spaced repetition is far more effective than solving random problems and hoping the patterns stick.

Related posts

• Maximum Subarray - The foundation of tracking best subarrays, here extended to three non-overlapping windows
• Best Time to Buy and Sell Stock III - Same left-right decomposition pattern applied to at most two transactions
• Split Array Largest Sum - Another problem about partitioning an array into fixed-count segments with an optimization goal