LeetCode 689: Maximum Sum of 3 Non-Overlapping Subarrays Solution in Python – A Step-by-Step Guide

What Is LeetCode 689: Maximum Sum of 3 Non-Overlapping Subarrays?

In LeetCode 689: Maximum Sum of 3 Non-Overlapping Subarrays, you’re given an integer array nums and an integer k, and your task is to find three non-overlapping subarrays, each of length k, that maximize their total sum. Return an array of their starting indices in ascending order; if multiple solutions exist, return the lexicographically smallest one. For example, with nums = [1, 2, 1, 2, 6, 7, 5, 1] and k = 2, the optimal subarrays are [1, 2], [2, 6], and [7, 5] (sum = 16), starting at indices [0, 3, 5], so return [0, 3, 5]. This problem tests your ability to optimize subarray selection efficiently.

Problem Statement

• Input:
• nums: List of integers.
• k: Integer (length of each subarray).
• Output: A list of 3 integers—starting indices of the 3 subarrays maximizing sum.
• Rules:
• Subarrays must be non-overlapping.
• Each subarray has length k.
• Maximize total sum of the 3 subarrays.
• Return indices in ascending order, lexicographically smallest if tied.

Constraints

• 1 ≤ nums.length ≤ 2 × 10⁴.
• 1 ≤ nums[i] ≤ 10⁵.
• 1 ≤ k ≤ floor(nums.length / 3).

Examples

• Input: nums = [1, 2, 1, 2, 6, 7, 5, 1], k = 2
• Output: [0, 3, 5] (Sum = 1+2 + 2+6 + 7+5 = 16)
• Input: nums = [1, 2, 1, 2, 1, 2, 1, 2], k = 2
• Output: [0, 2, 4] (Sum = 1+2 + 1+2 + 1+2 = 9)
• Input: nums = [4, 5, 10, 6, 11, 17, 4, 2], k = 2
• Output: [1, 3, 5] (Sum = 5+10 + 6+11 + 17+4 = 52)

These examples set the array—let’s solve it!

Understanding the Problem: Maximizing Three Subarrays

To solve LeetCode 689: Maximum Sum of 3 Non-Overlapping Subarrays in Python, we need to find three non-overlapping subarrays of length k in nums that maximize their total sum, returning their starting indices in ascending order. A brute-force approach—trying all possible triplets—would be O(n³), inefficient for n ≤ 2 × 10⁴. Since we’re optimizing fixed-length subarrays, a sliding window with prefix sums or exhaustive enumeration can work. We’ll use:

• Best Solution (Sliding Window with Prefix Sums): O(n) time, O(n) space—fast and optimal.
• Alternative Solution (Brute-Force with All Combinations): O(n³) time, O(1) space—simple but slow.

Let’s start with the sliding window solution, breaking it down for beginners.

Best Solution: Sliding Window with Prefix Sums

Why This Is the Best Solution

The sliding window with prefix sums approach is the top choice for LeetCode 689 because it’s highly efficient—O(n) time with O(n) space—and uses a clever strategy: precompute subarray sums and track the maximum sum achievable with 1, 2, and 3 subarrays using sliding windows, ensuring non-overlap and lexicographical order. It fits constraints (n ≤ 2 × 10⁴) perfectly and is intuitive once you see the prefix logic. It’s like sliding a treasure map to spot the best three caches in one sweep!

How It Works

Think of this as a treasure slider:

• Step 1: Compute Window Sums:
• window_sums[i]: Sum of subarray starting at i with length k.
• Step 2: Track Max Sums:
• left[i]: Max sum of one subarray from 0 to i-k+1, with index.
• middle[i]: Max sum of two subarrays from 0 to i-k+1, with indices.
• total[i]: Max sum of three subarrays from 0 to i, with indices.
• Step 3: Slide and Update:
• For each i:
• Update left with max sum up to i-k+1.
• Update middle with left + current window.
• Update total with middle + current window.
• Step 4: Return Result:
• Indices from max total sum.

It’s like a sum scanner—slide and maximize!

Step-by-Step Example

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

• Step 1: Window sums:
• [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.
• window_sums = [3, 3, 3, 8, 13, 12, 6].
• Step 2: Init arrays:
• left = [(sum, idx)], middle = [(sum, idx1, idx2)], total = [(sum, idx1, idx2, idx3)].
• Step 3: Slide:
• i=0: left=[(3, 0)].
• i=1: left=[(3, 0)].
• i=2: left=[(3, 0)], middle=[(6, 0, 2)].
• i=3: left=[(8, 3)], middle=[(11, 0, 3)].
• i=4: left=[(13, 4)], middle=[(16, 0, 4)], total=[(19, 0, 2, 4)].
• i=5: left=[(13, 4)], middle=[(16, 0, 4)], total=[(25, 0, 3, 5)].
• i=6: left=[(13, 4)], middle=[(19, 0, 5)], total=[(25, 0, 3, 5)].
• Step 4: Max total = 25 at [0, 3, 5], return [0, 3, 5].
• Output: [0, 3, 5].

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained clearly:

Copy codeclass Solution:
    def maxSumOfThreeSubarrays(self, nums: List[int], k: int) -> List[int]:
        # Step 1: Compute window sums
        n = len(nums)
        window_sums = []
        curr_sum = sum(nums[:k])
        window_sums.append(curr_sum)
        for i in range(k, n):
            curr_sum = curr_sum + nums[i] - nums[i - k]
            window_sums.append(curr_sum)

        # Step 2: Initialize arrays for max sums
        w = len(window_sums)  # Number of windows
        left = [(0, -1)] * w  # (sum, index)
        left[0] = (window_sums[0], 0)
        for i in range(1, w):
            if window_sums[i] > left[i - 1][0]:
                left[i] = (window_sums[i], i)
            else:
                left[i] = left[i - 1]

        right = [(0, -1)] * w
        right[-1] = (window_sums[-1], w - 1)
        for i in range(w - 2, -1, -1):
            if window_sums[i] >= right[i + 1][0]:  # >= for lexicographical order
                right[i] = (window_sums[i], i)
            else:
                right[i] = right[i + 1]

        # Step 3: Find max sum of three subarrays
        max_sum = 0
        result = []
        for i in range(k, w - k):  # Middle window range
            left_sum, left_idx = left[i - k]
            right_sum, right_idx = right[i + k]
            curr_sum = window_sums[i]
            total = left_sum + curr_sum + right_sum
            if total > max_sum:
                max_sum = total
                result = [left_idx, i, right_idx]

        # Step 4: Return result
        return result

• Lines 4-11: Window sums: Compute k-length sums with sliding window.
• Lines 14-26: Max sums:
• left: Max sum left of i.
• right: Max sum right of i, preferring leftmost index.
• Lines 29-38: Find max:
• For each middle i, combine with best left and right, update if max.
• Line 41: Return indices.
• Time Complexity: O(n)—single pass for sums and updates.
• Space Complexity: O(n)—arrays for sums.

This is like a treasure mapper—slide and max!

Alternative Solution: Brute-Force with All Combinations

Why an Alternative Approach?

The brute-force with all combinations approach tries every triplet—O(n³) time, O(1) space. It’s simpler, checking all possible non-overlapping subarrays, but inefficient for large n. It’s like digging up every spot to find the best three caches!

How It Works

Picture this as a triple picker:

• Step 1: Iterate all triplets of indices.
• Step 2: Check non-overlap:
• Ensure gaps ≥ k between starts.
• Step 3: Compute sum, track max:
• Update if sum exceeds current max.
• Step 4: Return indices.

It’s like a combo tester—pick and sum!

Step-by-Step Example

Example: Same as above

• Step 1: Triplets:
• (0, 2, 4): [1,2], [1,2], [6,7], sum=12.
• (0, 3, 5): [1,2], [2,6], [7,5], sum=16.
• (1, 3, 5): [2,1], [2,6], [7,5], sum=13.
• Step 2: Non-overlap checked.
• Step 3: Max sum = 16 at [0, 3, 5].
• Step 4: Return [0, 3, 5].
• Output: [0, 3, 5].

Code for Brute-Force Approach

Copy codeclass Solution:
    def maxSumOfThreeSubarrays(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)
        max_sum = 0
        result = []

        # Step 1: Iterate all triplets
        for i in range(n - 2 * k + 1):
            sum1 = sum(nums[i:i + k])
            for j in range(i + k, n - k + 1):
                sum2 = sum(nums[j:j + k])
                for m in range(j + k, n - k + 1):
                    sum3 = sum(nums[m:m + k])
                    total = sum1 + sum2 + sum3
                    if total > max_sum:
                        max_sum = total
                        result = [i, j, m]

        # Step 2: Return result
        return result

• Lines 4-6: Init: Max sum and result.
• Lines 9-17: Triplets:
• Compute sums, update max and indices if better.
• Line 20: Return result.
• Time Complexity: O(n³)—three nested loops.
• Space Complexity: O(1)—minimal extra space.

It’s a triple summer—check and max!

Comparing the Two Solutions

• Sliding Window (Best):
• Pros: O(n) time, O(n) space, fast and scalable.
• Cons: Prefix logic less obvious.
• Brute-Force (Alternative):
• Pros: O(n³) time, O(1) space, straightforward.
• Cons: Much slower.

Sliding window wins for efficiency.

Additional Examples and Edge Cases

• Input: nums = [1, 1, 1], k = 1
• Output: [0, 1, 2].
• Input: nums = [1, 2, 3, 4], k = 2
• Output: [0, 2, -1] (invalid k, but problem assumes valid).

Sliding window handles these well.

Complexity Breakdown

• Sliding Window: Time O(n), Space O(n).
• Brute-Force: Time O(n³), Space O(1).

Sliding window is optimal.

Key Takeaways

• Sliding Window: Sum sliding—smart!
• Brute-Force: Combo checking—clear!
• Subarrays: Maximizing is fun.
• Python Tip: Windows rock—see Python Basics.

Final Thoughts: Unearth That Treasure

LeetCode 689: Maximum Sum of 3 Non-Overlapping Subarrays in Python is a fun optimization challenge. Sliding window with prefix sums offers speed and elegance, while brute-force provides a clear baseline. Want more? Try LeetCode 53: Maximum Subarray or LeetCode 209: Minimum Size Subarray Sum. Ready to dig? Head to Solve LeetCode 689 on LeetCode and find those subarrays today!