0555HardArrayDynamic ProgrammingSliding WindowPrefix Sum

Three Blocks on the Support Rota

Tracked in this browser only

Trains the technique from

LeetCode 689Maximum Sum of 3 Non-Overlapping Subarrays

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A support desk has an hour-by-hour record of how many calls arrived, given as nums, so nums[i] is the call count for hour i.

The rota needs three shifts, each covering exactly k consecutive hours. No hour may belong to two shifts, and the shifts are reported in the order they occur.

Return the three starting hours as a list [a, b, c] with a + k <= b and b + k <= c, chosen so that the total call count across the three shifts is as large as it can be.

Several triples may reach that largest total. In that case return the smallest triple when the three lists are compared entry by entry: the smallest a, then among those the smallest b, then among those the smallest c.

Examples

Example 1

Input: nums = [1, 10, 10, 1, 1, 2, 2, 1, 1, 10, 10, 1], k = 2
Output: [1, 5, 9]

The shifts start at hours 1, 5 and 9. Each covers two hours, hour 1 does not reach hour 5 and hour 5 does not reach hour 9, so nothing overlaps. Their call counts are 20, 4 and 20, a total of 44.

Example 2

Input: nums = [3, 1, 3, 1, 3, 1, 3], k = 1
Output: [0, 2, 4]

With one-hour shifts the counts picked are 3, 3 and 3, a total of 9. Other triples also reach 9, and comparing them entry by entry makes [0, 2, 4] the smallest.

Example 3

Input: nums = [4, 4, 4, 4, 4, 4, 4, 4, 4], k = 3
Output: [0, 3, 6]

Every hour has the same count, so any three three-hour shifts total 36. Only one arrangement fits nine hours, and it starts at 0, 3 and 6.

Constraints

1 <= nums.length <= 2 * 10^4
1 <= nums[i] < 2^16
1 <= k <= floor(nums.length / 3)

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def max_sum_of_three_subarrays(nums: list[int], k: int) -> list[int]:

Java

public int[] maxSumOfThreeSubarrays(int[] nums, int k)

The intended approach

Time O(n): the rolling window and both lookup tables are single passes, and the final walk is another.Space O(n) for the shift totals and the two lookup tables.

Roll a window of `k` hours across the record once, adding the entering hour and dropping the leaving one, to get the call count of every possible shift. Then build two lookup tables over those shift totals: one giving, for each position, the best shift starting at or before it, and one giving the best shift starting at or after it. Both tables resolve a tie toward the earlier start, which is what makes the tables hand back the smallest indices available. Finally walk every legal middle start in increasing order, pair it with the table entries `k` hours to either side, and keep a triple only when its total strictly beats the best so far. Because the walk goes forward and only strict improvements replace the answer, the surviving triple is the smallest one at the best total.

Pythonentry point: max_sum_of_three_subarrays

def max_sum_of_three_subarrays(nums, k):
    # O(n) time, O(n) space. Roll a window of k hours across the day once to get
    # every block total. Then precompute, for each cut, the best block starting at
    # or before it and the best block starting at or after it, both resolving a tie
    # toward the earlier start. Finally try each legal middle start in increasing
    # order and keep a triple only when it strictly beats the best so far, which
    # settles ties on the smallest list.
    n = len(nums)
    m = n - k + 1
    block = [0] * m
    running = 0
    for i in range(k):
        running += nums[i]
    block[0] = running
    for i in range(1, m):
        running += nums[i + k - 1] - nums[i - 1]
        block[i] = running
    before = [0] * m
    pick = 0
    for i in range(m):
        if block[i] > block[pick]:
            pick = i
        before[i] = pick
    after = [0] * m
    pick = m - 1
    for i in range(m - 1, -1, -1):
        if block[i] >= block[pick]:
            pick = i
        after[i] = pick
    answer = None
    top = -1
    for mid in range(k, m - k):
        lo = before[mid - k]
        hi = after[mid + k]
        total = block[lo] + block[mid] + block[hi]
        if total > top:
            top = total
            answer = [lo, mid, hi]
    return answer

The obvious version

Add up every shift directly, then try all three starts by nested loops that keep the required gaps. Track the best total, and on a tie compare the candidate triple against the stored one entry by entry and keep the smaller.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_max_sum_of_three_subarrays(nums, k):
    n = len(nums)
    m = n - k + 1
    block = []
    for i in range(m):
        s = 0
        for j in range(i, i + k):
            s += nums[j]
        block.append(s)
    top = None
    answer = None
    for a in range(m):
        for b in range(a + k, m):
            for c in range(b + k, m):
                total = block[a] + block[b] + block[c]
                triple = [a, b, c]
                if top is None or total > top or (total == top and triple < answer):
                    top = total
                    answer = triple
    return answer

How this problem was checked

Reference solution executed against 12 test cases — 12 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in