What is the brute force approach and complexity for Maximum Sum of 3 Non-Overlapping Subarrays?

Check every valid triple a < b < c and keep the best total with time complexity O(N^3) and space complexity O(N).

What is the optimal approach and complexity for Maximum Sum of 3 Non-Overlapping Subarrays?

Build left[] and right[] in one pass each, then try each middle with two lookups with optimal time complexity O(N) and space complexity O(N).

Maximum Sum of 3 Non-Overlapping Subarrays

Q: What is the optimal approach and complexity for Maximum Sum of 3 Non-Overlapping Subarrays?

Build left[] and right[] in one pass each, then try each middle with two lookups with optimal time complexity O(N) and space complexity O(N).

Q: How do you identify the pattern for Maximum Sum of 3 Non-Overlapping Subarrays?

Look for key signals in the prompt: "three subarrays of length k" indicates The window size is fixed, so compute every window sum once and work with the array of sums.; "do not overlap" indicates The starts must be at least k apart, so the middle window splits the array into a left side and a right side.; "lexicographically smallest" indicates Ties need a rule. Strict > keeps the earlier answer, and both side arrays must use the same rule..

Hard·LeetCode #689 Pro OnlyInterview-Level

LeetCode

Problem Statement

You are given an integer array nums and an integer k. Pick three subarrays of length k that do not overlap: no index may belong to two of them. Choose them so that the total of their sums is as large as possible.

Return the starting indices of the three subarrays, in increasing order (0-indexed). If several choices give the same total, return the lexicographically smallest answer: compare the first index, then the second, then the third.

Input

An integer array nums and an integer k.

Output

Three starting indices [a, b, c] of non-overlapping length-k subarrays with the largest total sum, lexicographically smallest on a tie.

Example 1

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

Output: [0, 3, 5]

The windows [1, 2], [2, 6] and [7, 5] start at 0, 3 and 5. Their sums are 3, 8 and 12, a total of 23. [1, 3, 5] has the same total, but [0, 3, 5] is smaller.

Example 2

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

Output: [0, 2, 4]

Every window of length 2 sums to 3, so any three windows that do not overlap give the same total. [0, 2, 4] is the smallest choice.

Constraints

• 1 ≤ nums.length ≤ 2 × 10^4
• 1 ≤ nums[i] < 2^16
• 1 ≤ k ≤ floor(nums.length / 3)

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“three subarrays of length k”

→ The window size is fixed, so compute every window sum once and work with the array of sums.

“do not overlap”

→ The starts must be at least k apart, so the middle window splits the array into a left side and a right side.

“lexicographically smallest”

→ Ties need a rule. Strict > keeps the earlier answer, and both side arrays must use the same rule.

Approach Complexity Ladder

Brute Force — try every triple of startsO(N^3)O(N)

Check every valid triple a < b < c and keep the best total

Better — for each middle, scan both sidesO(N^2)O(N)

For each middle window, scan the left and the right for their best start

Optimal — precompute the best left and best rightO(N)O(N)

Build left[] and right[] in one pass each, then try each middle with two lookups

Brute Force Intuition

Compute every window sum W[s] first. Then try every triple of starts where each pair is at least k apart. Keep the best total. A tie keeps the earlier triple, which is the lexicographically smaller one.

Recognition rule for this sub-pattern:

Walk the days carrying the best value for each state (holding / not holding), or the best choice so far from each side.

Remember this · DP — Kadane / Subarray

Trigger

Maximum (or minimum) sum/product of a contiguous subarray, stock buy/sell, circular arrays.

Think

Is the best subarray ending at i either "i alone" or "best ending at i−1, plus i"?

Key question

Should I extend or restart?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like DP — Kadane / Subarray translate into production architectures and low-level memory mechanics.

LLD Architecture