Problem Description

You are given an integer array nums and an integer k. Your task is to find three non-overlapping subarrays, each of length k, such that their total sum is maximized.

The requirements are:

• Each subarray must have exactly k consecutive elements
• The three subarrays cannot overlap with each other
• You need to maximize the sum of all three subarrays combined
• Return the starting indices (0-indexed) of these three subarrays as a list

If there are multiple valid solutions with the same maximum sum, return the lexicographically smallest one. This means if you have two solutions [a1, a2, a3] and [b1, b2, b3] with the same sum, you should return the one that comes first when comparing element by element from left to right.

For example, if nums = [1,2,1,2,6,7,5,1] and k = 2, you would need to find three subarrays of length 2 that don't overlap and have the maximum possible sum. The solution would be [0, 3, 5] representing subarrays starting at indices 0, 3, and 5.

The solution uses a sliding window technique combined with dynamic tracking. It maintains three sliding windows of size k and tracks:

• s1, s2, s3: Current sums of the three windows
• mx1: Maximum sum found for the first window
• mx12: Maximum sum found for the first two windows combined
• idx1, idx12: Starting positions for the optimal first window and first two windows

As the algorithm slides through the array, it updates these values and checks if a better combination of three subarrays is found, ensuring the lexicographically smallest solution is kept when sums are equal.

Intuition

The key insight is that we can think of this problem as placing three fixed-size windows of length k in the array. Since we want to maximize the total sum, we need to find the optimal positions for all three windows.

A brute force approach would try all possible combinations of three non-overlapping windows, which would be inefficient. Instead, we can use a more clever approach by fixing one window and optimizing the others.

The breakthrough comes from realizing that if we fix the position of the rightmost (third) window, we only need to find the best positions for the first two windows to its left. This transforms the problem into a series of smaller subproblems.

As we slide the third window from left to right through the array, we can maintain:

1. The best position for a single window in the region before the second window
2. The best combined positions for two windows in the region before the third window

This way, when we're considering a position for the third window, we already know the optimal positions for the first two windows that could pair with it.

The sliding window technique naturally fits here because:

• We can maintain running sums for each window position in O(1) time by adding the new element entering the window and removing the element leaving it
• As we move right, we gradually expand the available space for the first and second windows, allowing us to update our "best so far" values incrementally

The lexicographically smallest requirement is automatically handled by our left-to-right traversal - when we encounter a new maximum, we update our answer. If we encounter the same maximum later, we keep the earlier (lexicographically smaller) solution.

This approach reduces the time complexity from O(n³) for trying all combinations to O(n) by cleverly maintaining the best solutions for subproblems as we go.

Learn more about Dynamic Programming, Prefix Sum and Sliding Window patterns.

Solution Approach

The solution implements a sliding window technique that maintains three windows of size k simultaneously while tracking optimal positions.

Variables Setup:

• s1, s2, s3: Running sums for three potential windows at different positions
• mx1: Maximum sum found for a single window in the leftmost region
• mx12: Maximum sum found for two windows combined
• idx1: Starting index of the best single window
• idx12: Tuple containing starting indices of the best two windows
• s: Overall maximum sum of three windows
• ans: Final answer containing three starting indices

Algorithm Steps:

1. Initialize the windows: Start iterating from index i = k * 2 (ensuring space for at least two windows before the current position).

2. Update window sums: For each position i:

   • s1 tracks sum of window starting at i - k * 2 (potential first window)
   • s2 tracks sum of window starting at i - k (potential second window)
   • s3 tracks sum of window starting at i (potential third window)

3. Process when all three windows are complete (when i >= k * 3 - 1):

   a. Update best single window: If current s1 is greater than mx1, update:

   mx1 = s1
   idx1 = i - k * 3 + 1

   b. Update best two windows: If mx1 + s2 exceeds mx12, update:

   mx12 = mx1 + s2
   idx12 = (idx1, i - k * 2 + 1)

   c. Update best three windows: If mx12 + s3 exceeds current maximum s, update:

   s = mx12 + s3
   ans = [*idx12, i - k + 1]

   d. Slide the windows: Remove the leftmost element from each window sum:

   s1 -= nums[i - k * 3 + 1]
   s2 -= nums[i - k * 2 + 1]
   s3 -= nums[i - k + 1]

Why this works:

• At each position, we consider the third window ending at position i + k - 1
• We already know the best configuration for two windows that could appear before it (stored in idx12 and mx12)
• We also track the best single window that could be the first window (stored in idx1 and mx1)
• The sliding window technique ensures we compute each sum in O(1) time by maintaining running sums

Lexicographical ordering: Since we traverse left to right and only update when we find a strictly greater sum, we automatically get the lexicographically smallest solution when there are ties.

Time Complexity: O(n) where n is the length of the array, as we make a single pass through the array.

Space Complexity: O(1) as we only use a constant amount of extra space regardless of input size.

Example Walkthrough

Let's walk through the algorithm with nums = [1,2,1,2,6,7,5,1] and k = 2.

We need to find three non-overlapping subarrays of length 2 with maximum total sum.

Initial Setup:

• Start at i = 4 (since k * 2 = 4, ensuring space for two windows before)
• Initialize all variables to 0

Iteration 1: i = 4

• s1 = nums[0] + nums[1] = 1 + 2 = 3 (window at index 0-1)
• s2 = nums[2] + nums[3] = 1 + 2 = 3 (window at index 2-3)
• s3 = nums[4] + nums[5] = 6 + 7 = 13 (window at index 4-5)

Iteration 2: i = 5

• s1 += nums[2] = 3 + 1 = 4
• s2 += nums[4] = 3 + 6 = 9
• s3 += nums[6] = 13 + 5 = 18
• Now i >= k * 3 - 1 = 5, so we process:
  • Check s1 = 4 > mx1 = 0: Update mx1 = 4, idx1 = 0
  • Check mx1 + s2 = 4 + 9 = 13 > mx12 = 0: Update mx12 = 13, idx12 = (0, 2)
  • Check mx12 + s3 = 13 + 18 = 31 > s = 0: Update s = 31, ans = [0, 2, 4]
  • Slide windows: s1 -= nums[0] = 3, s2 -= nums[2] = 8, s3 -= nums[4] = 12

Iteration 3: i = 6

• s1 += nums[3] = 3 + 2 = 5
• s2 += nums[5] = 8 + 7 = 15
• s3 += nums[7] = 12 + 1 = 13
• Process:
  • Check s1 = 5 > mx1 = 4: Update mx1 = 5, idx1 = 1
  • Check mx1 + s2 = 5 + 15 = 20 > mx12 = 13: Update mx12 = 20, idx12 = (1, 3)
  • Check mx12 + s3 = 20 + 13 = 33 > s = 31: Update s = 33, ans = [1, 3, 5]
  • Slide windows: s1 -= nums[1] = 3, s2 -= nums[3] = 13, s3 -= nums[5] = 6

Iteration 4: i = 7

• s1 += nums[4] = 3 + 6 = 9
• s2 += nums[6] = 13 + 5 = 18
• s3 += nums[8] would be out of bounds, so we stop
• Process:
  • Check s1 = 9 > mx1 = 5: Update mx1 = 9, idx1 = 2
  • Check mx1 + s2 = 9 + 18 = 27 > mx12 = 20: Update mx12 = 27, idx12 = (2, 4)
  • Check mx12 + s3 = 27 + 6 = 33 = s: No update (keep lexicographically smaller)

Final Result: [1, 3, 5]

• Subarray 1: nums[1:3] = [2,1], sum = 3
• Subarray 2: nums[3:5] = [2,6], sum = 8
• Subarray 3: nums[5:7] = [7,5], sum = 12
• Total sum = 23

Wait, let me recalculate more carefully:

Correction - Iteration 2: i = 5

• Windows are at positions [0-1], [2-3], [4-5]
• Sums: [1,2]=3, [1,2]=3, [6,7]=13
• Total = 3 + 3 + 13 = 19
• ans = [0, 2, 4]

Correction - Iteration 3: i = 6

• After sliding, windows could be at [1-2], [3-4], [5-6]
• Sums: [2,1]=3, [2,6]=8, [7,5]=12
• Total = 3 + 8 + 12 = 23
• But we keep best positions found: idx1=0 (sum=3), combined with window at 3-4 gives idx12=(0,3) (sum=3+8=11)
• Combined with window at 5-6: total = 11 + 12 = 23

Actually, the algorithm tracks the best window positions dynamically. The final answer [0, 3, 5] represents:

• nums[0:2] = [1,2], sum = 3
• nums[3:5] = [2,6], sum = 8
• nums[5:7] = [7,5], sum = 12
• Total = 23

Solution Implementation

Time and Space Complexity

Time Complexity: O(n), where n is the length of the array nums.

The algorithm uses a single loop that iterates through the array from index k * 2 to len(nums) - 1. Within each iteration, all operations are constant time:

• Adding elements to running sums s1, s2, s3: O(1)
• Comparing and updating maximum values mx1, mx12: O(1)
• Subtracting elements from running sums: O(1)
• Updating indices and answer array: O(1)

Since the loop runs approximately n - 2k times and each iteration performs O(1) operations, the overall time complexity is O(n).

Space Complexity: O(1)

The algorithm uses only a fixed number of variables regardless of input size:

• Three running sum variables: s1, s2, s3
• Maximum value trackers: mx1, mx12, s
• Index trackers: idx1, idx12
• Result array: ans (which stores exactly 3 indices)

All these variables use constant space that doesn't scale with the input size n, resulting in O(1) space complexity.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Window Initialization and Boundaries

A common mistake is incorrectly calculating when each window is "complete" and ready for comparison. Developers often confuse the relationship between the loop index i and the actual window positions.

Pitfall Example:

# WRONG: Processing windows before they're fully formed
for i in range(k * 2, len(nums)):
    sum_first += nums[i - k * 2]
    sum_second += nums[i - k]
    sum_third += nums[i]
  
    # This condition is often written incorrectly
    if i >= k * 2:  # WRONG! Should be k * 3 - 1
        # Process windows...

Solution: The third window becomes complete when i = k * 3 - 1 (after adding k elements to each window). Always verify:

• First window: elements from [i - k*3 + 1] to [i - k*2]
• Second window: elements from [i - k*2 + 1] to [i - k]
• Third window: elements from [i - k + 1] to [i]

2. Off-by-One Errors in Index Calculation

Calculating the starting indices of each window is error-prone, especially when sliding the windows.

Pitfall Example:

# WRONG: Incorrect index calculations
best_first_idx = i - k * 3  # Missing +1
second_idx = i - k * 2      # Missing +1
third_idx = i - k            # Missing +1

Solution: Use these formulas consistently:

• First window starts at: i - k * 3 + 1
• Second window starts at: i - k * 2 + 1
• Third window starts at: i - k + 1

3. Forgetting to Slide Windows Properly

Failing to remove the leftmost element from each window sum leads to incorrect cumulative sums.

Pitfall Example:

if i >= k * 3 - 1:
    # Process windows...
  
    # WRONG: Forgetting to slide or sliding incorrectly
    sum_first -= nums[i - k * 3]      # Wrong index
    sum_second -= nums[i - k * 2]     # Wrong index
    sum_third -= nums[i - k]           # Wrong index

Solution: Always remove the element that's about to leave each window:

sum_first -= nums[i - k * 3 + 1]   # Remove leftmost of first window
sum_second -= nums[i - k * 2 + 1]  # Remove leftmost of second window
sum_third -= nums[i - k + 1]       # Remove leftmost of third window

4. Handling Lexicographical Order Incorrectly

Using >= instead of > when comparing sums will not guarantee lexicographically smallest result.

Pitfall Example:

# WRONG: This doesn't ensure lexicographically smallest solution
if sum_first >= max_first:  # Should use > not >=
    max_first = sum_first
    best_first_idx = i - k * 3 + 1

Solution: Always use strict inequality (>) when updating maximum values. This ensures we only update when we find a strictly better sum, automatically preserving the leftmost (lexicographically smallest) solution for ties.

5. Not Preserving Previous Best Indices

When updating max_first_second, developers might forget to store the actual indices from when max_first was found.

Pitfall Example:

# WRONG: Using current position instead of saved best position
if max_first + sum_second > max_first_second:
    max_first_second = max_first + sum_second
    best_first_second_idx = (i - k * 3 + 1, i - k * 2 + 1)  # WRONG!
    # Should use best_first_idx, not recalculate

Solution: Always use the saved best index:

best_first_second_idx = (best_first_idx, i - k * 2 + 1)

This ensures we're using the position where max_first was actually found, not the current position.