Maximum Sum of 3 Non-Overlapping Subarrays
HardPrompt
Given an integer array nums and an integer k, find three non-overlapping subarrays of length k with maximum sum and return them.
Return the result as a list of indices representing the starting position of each interval (0-indexed). If there are multiple answers, return the lexicographically smallest one.
Example 1:
Input: nums = [1,2,1,2,6,7,5,1], k = 2
Output: [0,3,5]
Explanation: Subarrays [1, 2], [2, 6], [7, 5] correspond to the starting indices [0, 3, 5].
We could have also taken [2, 1], but an answer of [1, 3, 5] would be lexicographically larger.Example 2:
Input: nums = [1,2,1,2,1,2,1,2,1], k = 2
Output: [0,2,4]
Constraints:
1 <= nums.length <= 2 * 1041 <= nums[i] < 2161 <= k <= floor(nums.length / 3)
Approaches
3 approaches with complexity analysis and trade-offs.
This approach involves checking every possible combination of three non-overlapping subarrays of length k. To make the sum calculation for each subarray efficient, we first pre-compute the sums of all possible subarrays of length k and store them. Then, we use three nested loops to find the combination of three subarrays that yields the maximum total sum.
Algorithm
- Create an array
sumswheresums[i]stores the sum of the subarray of lengthkstarting at indexi. This is computed in O(n) time using a sliding window. - Initialize
maxSumto 0 andresultto store the three indices. - Use three nested loops to iterate through all valid combinations of starting indices
i,j, andl.- The outer loop for
iruns from0ton - 3k. - The middle loop for
jruns fromi + kton - 2k. - The inner loop for
lruns fromj + kton - k.
- The outer loop for
- Inside the loops, calculate the total sum
sums[i] + sums[j] + sums[l]. - If the current sum is greater than
maxSum, updatemaxSumand theresultindices. - Because the loops iterate through indices in increasing order, the first combination found for a maximum sum will be the lexicographically smallest.
Walkthrough
The most straightforward way to solve this problem is to try every single valid triplet of starting indices (i, j, l). A subarray of length k can start at any index from 0 to n-k. For three non-overlapping subarrays, the starting indices must satisfy 0 <= i < j < l, j >= i + k, and l >= j + k.
To avoid re-calculating the sum of each subarray in O(k) time within the loops, we can pre-calculate these sums. We create an array, let's call it sums, where sums[x] holds the sum of elements from nums[x] to nums[x+k-1]. This sums array can be populated in O(n) time using a sliding window.
After pre-computation, we iterate through all possible i, j, and l, find their corresponding sums from the sums array, and check if their total sum is the maximum found so far. The first set of indices that gives the maximum sum will be the lexicographically smallest due to the ordered iteration.
class Solution { public int[] maxSumOfThreeSubarrays(int[] nums, int k) { int n = nums.length; if (n < 3 * k) { return new int[0]; } long[] sums = new long[n - k + 1]; long currentSum = 0; for (int i = 0; i < n; i++) { currentSum += nums[i]; if (i >= k) { currentSum -= nums[i - k]; } if (i >= k - 1) { sums[i - k + 1] = currentSum; } } long maxSum = 0; int[] result = new int[3]; for (int i = 0; i <= n - 3 * k; i++) { for (int j = i + k; j <= n - 2 * k; j++) { for (int l = j + k; l <= n - k; l++) { long currentTotalSum = sums[i] + sums[j] + sums[l]; if (currentTotalSum > maxSum) { maxSum = currentTotalSum; result[0] = i; result[1] = j; result[2] = l; } } } } return result; }}Complexity
Time
O(n^3). Pre-computing the sums takes O(n), but the three nested loops dominate the runtime, making it cubic in the size of the input array.
Space
O(n) to store the pre-computed sums of all subarrays of length k.
Trade-offs
Pros
Simple to conceptualize and implement.
Cons
Extremely inefficient with a time complexity of O(n^3).
Will result in a 'Time Limit Exceeded' error for the given constraints.
This approach improves upon the brute-force method by reducing one level of loop nesting. We still iterate through possible starting positions for the first two subarrays, i and j. However, instead of a third loop for the third subarray, we pre-compute the best possible third subarray for any given starting point. This optimization reduces the time complexity from cubic to quadratic.
Algorithm
- First, compute the
sumsarray of all subarray sums of lengthkin O(n) time. - Create an auxiliary array,
rightMax, whererightMax[i]stores the starting index of the subarray with the maximum sum in the range[i, n-k]. This is computed in O(n) by iterating from right to left. - Initialize
maxSumand aresultarray. - Use two nested loops to fix the starting indices
iandjof the first two subarrays. - For each pair
(i, j), find the optimal third subarray's start indexlfromrightMax[j+k]. - Calculate the total sum
sums[i] + sums[j] + sums[l]and update themaxSumandresultif a better combination is found.
Walkthrough
We can optimize the O(n^3) solution by removing the innermost loop. The goal of the innermost loop for a fixed i and j is to find an index l >= j+k that maximizes sums[l]. This search can be optimized.
We can pre-compute an array, say rightMax, where rightMax[x] stores the index of the maximum value in the suffix of the sums array starting at x. This rightMax array can be computed in O(n) time by iterating backwards. To handle the lexicographical requirement, if two subarrays have the same maximum sum, we choose the one with the smaller starting index.
With sums and rightMax pre-computed, we only need two nested loops for i and j. For each pair (i, j), the best starting index for the third subarray, l, is simply rightMax[j+k]. This allows us to find the total sum in O(1) time inside the loops.
class Solution { public int[] maxSumOfThreeSubarrays(int[] nums, int k) { int n = nums.length; long[] sums = new long[n - k + 1]; long currentSum = 0; for (int i = 0; i < n; i++) { currentSum += nums[i]; if (i >= k) { currentSum -= nums[i - k]; } if (i >= k - 1) { sums[i - k + 1] = currentSum; } } int[] rightMax = new int[n - k + 1]; rightMax[n - k] = n - k; for (int i = n - k - 1; i >= 0; i--) { if (sums[i] >= sums[rightMax[i + 1]]) { rightMax[i] = i; } else { rightMax[i] = rightMax[i + 1]; } } long maxSum = 0; int[] result = new int[3]; for (int i = 0; i <= n - 3 * k; i++) { for (int j = i + k; j <= n - 2 * k; j++) { int l = rightMax[j + k]; long currentTotalSum = sums[i] + sums[j] + sums[l]; if (currentTotalSum > maxSum) { maxSum = currentTotalSum; result[0] = i; result[1] = j; result[2] = l; } } } return result; }}Complexity
Time
O(n^2). The pre-computation steps take O(n) time, but the two nested loops for indices `i` and `j` result in a quadratic time complexity.
Space
O(n) for storing the `sums` and `rightMax` arrays.
Trade-offs
Pros
Significantly more efficient than the O(n^3) brute-force approach.
Builds a good foundation for the fully optimal O(n) solution.
Cons
While better than brute force, it may still be too slow and time out for the largest possible inputs under the given constraints.
This is the most efficient approach, solving the problem in linear time using dynamic programming and pre-computation. The key insight is to iterate through all possible middle subarrays and, for each one, quickly find the best possible non-overlapping left and right subarrays. This is achieved by pre-computing the optimal choices for the left and right parts.
Algorithm
- Calculate the
sumsarray using a sliding window in O(n) time. - Create a
leftMaxarray whereleftMax[i]stores the index of the maximum sum insums[0...i]. Compute this in O(n) with a left-to-right pass. - Create a
rightMaxarray whererightMax[i]stores the index of the maximum sum insums[i...n-k]. Compute this in O(n) with a right-to-left pass, preferring smaller indices on ties for lexicographical order. - Initialize
maxSumand aresultarray. - Iterate with a single loop for the middle subarray's starting index
jfromkton - 2k. - For each
j, find the best left indexi = leftMax[j-k]and the best right indexl = rightMax[j+k]in O(1) time. - Calculate the total sum and update
maxSumandresultif a new maximum is found.
Walkthrough
This optimal solution is based on the idea of fixing the middle subarray and finding the best left and right subarrays efficiently. Let the middle subarray start at index j. It can range from k to n - 2k.
For a fixed j, the first subarray must start at an index i in [0, j-k], and the third subarray must start at an index l in [j+k, n-k]. To maximize the total sum sums[i] + sums[j] + sums[l], we need to maximize sums[i] and sums[l] independently.
We can pre-compute the answers for these subproblems:
leftMaxarray:leftMax[x]stores the index of the subarray with the maximum sum in the range[0, x]. This can be computed in O(n) with a single pass from left to right.rightMaxarray:rightMax[x]stores the index of the subarray with the maximum sum in the range[x, n-k]. This is computed in O(n) with a pass from right to left.
After computing the sums, leftMax, and rightMax arrays, we can iterate through each possible middle index j. For each j, the best left index is leftMax[j-k] and the best right index is rightMax[j+k]. We calculate the total sum and update our answer if it's a new maximum. This entire process takes only linear time and space.
class Solution { public int[] maxSumOfThreeSubarrays(int[] nums, int k) { int n = nums.length; if (n < 3 * k) { return new int[0]; } // Calculate sums of all subarrays of size k long[] sums = new long[n - k + 1]; long currentSum = 0; for (int i = 0; i < n; i++) { currentSum += nums[i]; if (i >= k) { currentSum -= nums[i - k]; } if (i >= k - 1) { sums[i - k + 1] = currentSum; } } // Calculate leftMax: leftMax[i] is the index of the max sum in sums[0...i] int[] leftMax = new int[sums.length]; int bestIndex = 0; for (int i = 0; i < sums.length; i++) { if (sums[i] > sums[bestIndex]) { bestIndex = i; } leftMax[i] = bestIndex; } // Calculate rightMax: rightMax[i] is the index of the max sum in sums[i...sums.length-1] int[] rightMax = new int[sums.length]; bestIndex = sums.length - 1; for (int i = sums.length - 1; i >= 0; i--) { // For lexicographically smallest, if sums are equal, choose smaller index. if (sums[i] >= sums[bestIndex]) { bestIndex = i; } rightMax[i] = bestIndex; } // Iterate through middle subarray start index j long maxSum = 0; int[] result = new int[3]; for (int j = k; j <= n - 2 * k; j++) { int i = leftMax[j - k]; int l = rightMax[j + k]; long currentTotalSum = sums[i] + sums[j] + sums[l]; if (currentTotalSum > maxSum) { maxSum = currentTotalSum; result[0] = i; result[1] = j; result[2] = l; } } return result; }}Complexity
Time
O(n). Each of the four main steps (calculating `sums`, `leftMax`, `rightMax`, and the final loop) takes O(n) time, leading to a linear overall time complexity.
Space
O(n) to store the `sums`, `leftMax`, and `rightMax` arrays.
Trade-offs
Pros
Optimal time complexity of O(n), making it very efficient for large inputs.
The logic of breaking down the problem by fixing the middle element is a powerful and reusable pattern.
Cons
Requires more space compared to a naive brute-force approach due to auxiliary arrays.
The logic is more complex to implement correctly compared to simpler approaches.
Solutions
Solution
class Solution {public int[] maxSumOfThreeSubarrays(int[] nums, int k) { int n = nums.length; int[] s = new int[n + 1]; for (int i = 0; i < n; ++i) { s[i + 1] = s[i] + nums[i]; } int[][] pre = new int[n][0]; int[][] suf = new int[n][0]; for (int i = 0, t = 0, idx = 0; i < n - k + 1; ++i) { int cur = s[i + k] - s[i]; if (cur > t) { pre[i + k - 1] = new int[]{cur, i}; t = cur; idx = i; } else { pre[i + k - 1] = new int[]{t, idx}; } } for (int i = n - k, t = 0, idx = 0; i >= 0; --i) { int cur = s[i + k] - s[i]; if (cur >= t) { suf[i] = new int[]{cur, i}; t = cur; idx = i; } else { suf[i] = new int[]{t, idx}; } } int[] ans = new int[0]; for (int i = k, t = 0; i < n - 2 * k + 1; ++i) { int cur = s[i + k] - s[i] + pre[i - 1][0] + suf[i + k][0]; if (cur > t) { ans = new int[]{pre[i - 1][1], i, suf[i + k][1]}; t = cur; } } return ans; }}class Solution {public: vector<int> maxSumOfThreeSubarrays(vector<int> &nums, int k) { int n = nums.size(); vector<int> s(n + 1, 0); for (int i = 0; i < n; ++i) { s[i + 1] = s[i] + nums[i]; } vector<vector<int>> pre(n, vector<int>(2, 0)); vector<vector<int>> suf(n, vector<int>(2, 0)); for (int i = 0, t = 0, idx = 0; i < n - k + 1; ++i) { int cur = s[i + k] - s[i]; if (cur > t) { pre[i + k - 1] = {cur, i}; t = cur; idx = i; } else { pre[i + k - 1] = {t, idx}; } } for (int i = n - k, t = 0, idx = 0; i >= 0; --i) { int cur = s[i + k] - s[i]; if (cur >= t) { suf[i] = {cur, i}; t = cur; idx = i; } else { suf[i] = {t, idx}; } } vector<int> ans; for (int i = k, t = 0; i < n - 2 * k + 1; ++i) { int cur = s[i + k] - s[i] + pre[i - 1][0] + suf[i + k][0]; if (cur > t) { ans = {pre[i - 1][1], i, suf[i + k][1]}; t = cur; } } return ans; }};class Solution: def maxSumOfThreeSubarrays(self, nums: List[int], k: int) -> List[int]: n = len(nums) s = list(accumulate(nums, initial=0)) pre = [[] for _ in range(n)] suf = [[] for _ in range(n)] t = idx = 0 for i in range(n - k + 1): if (cur: = s[i + k] - s[i]) > t: pre[i + k - 1] = [cur, i] t, idx = pre[i + k - 1] else: pre[i + k - 1] = [t, idx] t = idx = 0 for i in range(n - k, - 1, - 1): if (cur: = s[i + k] - s[i]) >= t: suf[i] = [cur, i] t, idx = suf[i] else: suf[i] = [t, idx] t = 0 ans = [] for i in range(k, n - 2 * k + 1): if (cur: = s[i + k] - s[i] + pre[i - 1][0] + suf[i + k][0]) > t: ans = [pre[i - 1][1], i, suf[i + k][1]] t = cur return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.