Problem

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.

Examples

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]

Solution

Method 1 - Sliding Window

Here is the approach:

  1. Compute the Sum of Every Subarray of Length k:
    • Use a sliding window approach to compute the sum for each subarray of length k.
  2. Find the Best Subarray Starting from the Left Up to Each Index:
    • Create a left array where left[i] contains the starting index of the subarray with the maximum sum up to and including index i.
  3. Find the Best Subarray Starting from the Right Up to Each Index:
    • Create a right array where right[i] contains the starting index of the subarray with the maximum sum starting from and including index i.
  4. Determine the Best Combination of Three Subarrays:
    • Iterate through the array to find the best combination of three non-overlapping subarrays by using the left, right, and precomputed sums.

Code

Java
public class Solution {
    public int[] maxSumOfThreeSubarrays(int[] nums, int k) {
        int n = nums.length;
        int[] sum = new int[n - k + 1];

        // Compute sum of each k-length subarray
        int windowSum = 0;
        for (int i = 0; i < k; i++) {
            windowSum += nums[i];
        }
        sum[0] = windowSum;
        for (int i = 1; i <= n - k; i++) {
            windowSum = windowSum - nums[i - 1] + nums[i + k - 1];
            sum[i] = windowSum;
        }

        // Find the left index with maximum sum
        int[] left = new int[n - k + 1];
        int bestLeft = 0;
        left[0] = 0;
        for (int i = 1; i <= n - k; i++) {
            if (sum[i] > sum[bestLeft]) {
                bestLeft = i;
            }
            left[i] = bestLeft;
        }

        // Find the right index with maximum sum
        int[] right = new int[n - k + 1];
        int bestRight = n - k;
        right[n - k] = n - k;
        for (int i = n - k - 1; i >= 0; i--) {
            if (sum[i] >= sum[bestRight]) {
                bestRight = i;
            }
            right[i] = bestRight;
        }

        // Find the max sum of three non-overlapping subarrays
        int maxSum = 0;
        int[] result = new int[3];
        for (int i = k; i <= n - 2 * k; i++) {
            int l = left[i - k], r = right[i + k];
            int total = sum[l] + sum[i] + sum[r];
            if (total > maxSum) {
                maxSum = total;
                result[0] = l;
                result[1] = i;
                result[2] = r;
            }
        }

        return result;
    }
}
Python
class Solution : def maxSumOfThreeSubarrays(self, nums: List[int], k: int) -> List[int]:
     n = len(nums)
     sum = [0] * (n - k + 1)

#Compute sum of each k - length subarray
     window_sum = sum(nums[:k])
     sum[0] = window_sum
     for i in range(1, n - k + 1):
         window_sum = window_sum - nums[i - 1] + nums[i + k - 1]
         sum[i] = window_sum

#Find the left index with maximum sum
     left = [0] * (n - k + 1)
     best_left = 0
     left[0] = 0
     for i in range(1, n - k + 1):
         if sum[i] > sum[best_left]:
             best_left = i
         left[i] = best_left

#Find the right index with maximum sum
     right = [0] * (n - k + 1)
     best_right = n - k
     right[n - k] = n - k
     for i in range(n - k - 1, -1, -1):
         if sum[i] >= sum[best_right]:
             best_right = i
         right[i] = best_right

#Find the max sum of three non - overlapping subarrays
     max_sum = 0
     result = [0] * 3
     for i in range(k, n - 2 * k + 1):
         l = left[i - k]
         r = right[i + k]
         total = sum[l] + sum[i] + sum[r]
         if total > max_sum:
             max_sum = total
             result[0] = l
             result[1] = i
             result[2] = r
     
     return result

Complexity

  • ⏰ Time complexity: O(n)
    • Computing the sum array takes O(n) where n is the length of nums.
    • Constructing the left and right arrays each take O(n).
    • The final iteration to find the best combination of three subarrays takes O(n).
  • 🧺 Space complexity: O(n), as we use additional arrays sum, left, and right, each of size O(n).