Two Separate Shifts
MediumSliding Window
Problem
A delivery company knows the number of orders expected each hour in nums. It will staff two shifts: one of exactly firstLen consecutive hours and one of exactly secondLen consecutive hours. The shifts must not overlap, but either one may come first.
Return the maximum total number of orders the two shifts can cover.
Example 1
- Input:
- nums = [3, 1, 8, 2, 7, 1, 4], firstLen = 1, secondLen = 2
- Output:
- 17
Cover hour 4 (7 orders) alone and hours 2–3 (8 + 2) together: 7 + 10 = 17. Hour 2 alone plus hours 3–4 is also 8 + 9 = 17.
Example 2
- Input:
- nums = [1, 2, 3], firstLen = 1, secondLen = 2
- Output:
- 6
Constraints
- 1 ≤ firstLen, secondLen
- firstLen + secondLen ≤ nums.length ≤ 10^4
- 0 ≤ nums[i] ≤ 1000
Hint
Show the first hint
Handle the two orders separately: the firstLen shift before the secondLen shift, and the reverse.
Walkthrough
How to approach it
01Clarify before coding
- Can the shifts touch? Yes, adjacent is fine, overlapping is not.
- Does it matter which shift comes first? No, try both orders.
- Values non-negative? Yes, but the method works with negatives too.
02Brute force
Enumerate every pair of non-overlapping windows and add their sums (prefix sums make each sum O(1)).
Cost: O(n²) pairs, 10^8 at n = 10^4; borderline and not what is expected.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.