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 smaller.
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)Problem Overview: You are given an integer array and a fixed length k. The goal is to pick three non-overlapping subarrays of length k such that their total sum is maximized. The output should be the starting indices of those three subarrays in lexicographically smallest order when multiple answers exist.
Approach 1: Prefix Sum with Sliding Window (O(n) time, O(n) space)
This approach precomputes the sum of every subarray of length k using a sliding window. First build a prefix sum array so any window sum can be calculated in constant time. Then maintain two helper arrays: left[i] stores the index of the best window from the start up to i, and right[i] stores the best window from i to the end. Iterate through possible middle windows and combine it with the best left and right windows that do not overlap. Each step performs constant work, so the full scan runs in O(n) time with O(n) extra space.
The key insight is separating the problem into three windows where the middle window is fixed while the left and right sides reuse previously computed optimal windows. This removes the need to test all combinations and turns a potentially cubic search into a linear pass. This method relies heavily on techniques from Array processing and the Sliding Window pattern.
Approach 2: Dynamic Programming with Sliding Window (O(n) time, O(n) space)
Dynamic programming can model the problem as choosing up to three windows while maximizing total sum. Precompute all window sums using a sliding window. Then build a DP table where dp[i][j] represents the maximum sum using j windows considering the first i positions. For each position, either skip the current window or take it and add the value from dp[i-k][j-1]. Tracking decisions allows reconstruction of the starting indices.
This method generalizes easily if the number of subarrays changes from three to m. The transition uses previously computed states and avoids overlapping by jumping back k positions whenever a window is chosen. The algorithm still runs in O(n) time for the fixed case of three windows and uses O(n) memory. It demonstrates core ideas from Dynamic Programming combined with window preprocessing.
Recommended for interviews: The prefix sum + sliding window approach is what most interviewers expect. It shows you understand how to precompute window sums and reuse optimal substructure with helper arrays. Explaining the brute-force intuition first (checking all triples of windows) shows problem understanding, but the linear-time window optimization demonstrates strong algorithmic thinking.
This approach uses a prefix sum array to quickly calculate the sum of any subarray and a sliding window technique to explore possible starting points for the subarrays.
This C solution uses three arrays:
prefix[] for prefix sums to compute subarray sums quickly.left[] to store the starting index of the max subarray sum from the left.right[] to store the starting index of the max subarray sum from the right.It iterates over potential middle subarray starting points and uses these auxiliary arrays to compute the total sum efficiently. Updates are made to get the largest sum and store associated index positions in result[].
Time Complexity: O(n), since we make a constant number of passes through the array.
Space Complexity: O(n), due to the prefix, left, and right arrays.
This approach employs dynamic programming alongside a sliding window to optimize subarray sum calculations and ensure non-overlapping conditions.
This C solution introduces a dynamic programming table (dp) to record the maximum sum up to each point. Using left and right tracking, it determines the best left and right subarrays. A single pass checks for optimal middle subarrays using this dynamic information.
Time Complexity: O(n), for traversal of the nums array multiple times.
Space Complexity: O(n), utilizing the dp, prefix, left, and right arrays.
We use a sliding window to enumerate the position of the third subarray, while maintaining the maximum sum and its position of the first two non-overlapping subarrays.
The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
We can preprocess to get the prefix sum array s of the array nums, where s[i] = sum_{j=0}^{i-1} nums[j]. Then for any i, j, s[j] - s[i] is the sum of the subarray [i, j).
Next, we use dynamic programming to maintain two arrays pre and suf of length n, where pre[i] represents the maximum sum and its starting position of the subarray of length k within the range [0, i], and suf[i] represents the maximum sum and its starting position of the subarray of length k within the range [i, n).
Then, we enumerate the starting position i of the middle subarray. The sum of the three subarrays is pre[i-1][0] + suf[i+k][0] + (s[i+k] - s[i]), where pre[i-1][0] represents the maximum sum of the subarray of length k within the range [0, i-1], suf[i+k][0] represents the maximum sum of the subarray of length k within the range [i+k, n), and (s[i+k] - s[i]) represents the sum of the subarray of length k within the range [i, i+k). We find the starting positions of the three subarrays corresponding to the maximum sum.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the array nums.
| Approach | Complexity |
|---|---|
| Prefix Sum with Sliding Window | Time Complexity: O(n), since we make a constant number of passes through the array. |
| Dynamic Programming with Sliding Window | Time Complexity: O(n), for traversal of the nums array multiple times. |
| Sliding Window | — |
| Preprocessing Prefix and Suffix + Enumerating Middle Subarray | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Prefix Sum with Sliding Window | O(n) | O(n) | Best general solution. Efficient for fixed 3-window problems and common in interviews. |
| Dynamic Programming with Sliding Window | O(n) | O(n) | Useful when extending the problem to select m non-overlapping subarrays. |
Maximum Sum of 3 Non-Overlapping Subarrays - Leetcode 689 - Python • NeetCodeIO • 13,363 views views
Watch 9 more video solutions →Practice Maximum Sum of 3 Non-Overlapping Subarrays with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor