Best Span Around a Day
HardTwo Pointers
Problem
A streaming service records daily viewer counts nums. A promo report must cover a contiguous span of days that includes day `k`. A span [i, j] scores min(nums[i..j]) · (j - i + 1): its weakest day times its length.
Return the highest score over all spans that contain k.
Example 1
- Input:
- nums = [2, 6, 4, 9, 3, 1], k = 2
- Output:
- 12
The span [1, 3] = [6, 4, 9] scores 4 · 3 = 12; [1, 4] = [6, 4, 9, 3] scores 3 · 4 = 12 too.
Example 2
- Input:
- nums = [5, 5, 1], k = 0
- Output:
- 10
[5, 5] scores 5 · 2 = 10; adding the 1 drops it to 3.
Constraints
- 1 ≤ nums.length ≤ 10^5
- 1 ≤ nums[i] ≤ 2·10^4
- 0 ≤ k < nums.length
Hint
Show the first hint
Every valid span grows outward from k. Think of extending it one day at a time.
Walkthrough
How to approach it
01Clarify before coding
- Must the span include day k? Yes, that is the only constraint.
- Can the span be just [k, k]? Yes, scoring nums[k].
- Can the score overflow 32 bits? Up to 2·10^4 · 10^5 = 2·10^9, beyond a signed 32-bit int in typed languages.
02Brute force
Try every i ≤ k ≤ j, computing the minimum incrementally as j grows for each i.
Cost: O(n²) time with incremental minima: 10^10 operations at the worst k.
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.