Maximize a Fixed-Length Sum over Sparse Constant Segments
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Online Assessment
# Maximize a Fixed-Length Sum over Sparse Constant Segments
Positive integer positions represent bags arranged from 1 to infinity. You are given non-overlapping closed segments. A segment `[left, right, value]` means every bag from `left` through `right` contains `value` units of money. Bags outside all segments contain zero.
Choose exactly `k` consecutive bags and maximize their total money. Compute the maximum using the full integer values, then return that maximum modulo `1,000,000,007`.
Implement:
```text
calculateMaximumConsecutiveSum(k, segments) -> integer
```
Segments may be supplied in any order. They never intersect, and every value is positive.
## Constraints
- `1 <= segments.length <= 200,000`
- `1 <= k <= 10^9`
- `1 <= left <= right <= 10^9`
- `1 <= value <= 10^6`
## Examples
### Example 1
```text
k = 5
segments = [[1, 4, 2], [6, 6, 5], [7, 7, 7], [9, 10, 1]]
output = 16
```
The window from bag 3 through bag 7 contains `2 + 2 + 0 + 5 + 7 = 16`.
### Example 2
```text
k = 3
segments = [[5, 7, 4], [2, 2, 10]]
output = 12
```
The window from bag 5 through bag 7 contains 12, which is greater than any length-three window containing bag 2.
Overview: Find the maximum sum of exactly k consecutive positions in an effectively infinite sparse array represented by non-overlapping constant-value segments. The prompt preserves large coordinate bounds, arbitrary segment order, zero-filled gaps, full-value maximization, and final modulo output.
Read the full Amazon Software Engineer interview experience this question came from
Implement calculateMaximumConsecutiveSum(k, segments). Positive integer bag positions start at 1 and continue without bound. Each non-overlapping closed segment [left, right, value] gives every bag in that range the positive value; all other bags contain zero. Segments may be in any order. Choose exactly k consecutive bags, maximize their sum using the full integer values, and only then return that maximum modulo 1,000,000,007.
Constraints
- 1 <= segments.length <= 200,000
- 1 <= k <= 10^9
- Every segment is [left, right, value] with 1 <= left <= right <= 10^9.
- Segments are pairwise non-overlapping and may be supplied in any order.
- 1 <= value <= 10^6; bags outside all segments contain zero.
- Choose exactly k consecutive positive-integer bag positions.
- Maximize with full integer values before returning modulo 1,000,000,007.
Examples
Input: (5, [[1, 4, 2], [6, 6, 5], [7, 7, 7], [9, 10, 1]])
Expected Output: 16
Explanation: The first source example selects bags 3 through 7 across a gap and three segments.
Input: (3, [[5, 7, 4], [2, 2, 10]])
Expected Output: 12
Explanation: The second source example favors the complete length-three segment.
Hints
- Compare two adjacent windows: one bag leaves at x and one enters at x + k.
- A constant range in the bag values becomes a constant range in the adjacent-window difference.
Community answers
Answer by 17amolgode
Exact Pattern Problem: LeetCode 3413 - Maximum Coins From K Consecutive Bags
https://leetcode.com/problems/maximum-coins-from-k-consecutive-bags/
Similar / Extended Practice:
LeetCode 2271 - Maximum White Tiles Covered by a Carpet
https://leetcode.com/problems/maximum-white-tiles-covered-by-a-carpet/
Extended the sliding-window approach from LC 2271 to weighted sparse ranges.
Instead of counting covered tiles, calculate (range length * value).
MOD = 10**9+7
def maximumCoinsHelper(coins: List[List[int]], k: int) -> int:
n = len(coins)
coins.sort() # <---- VIMP
START = 0
END = 1
VALUE = 2
left = 0
cur_sum = 0
max_res = 0
for right in range(n):
r_start = coins[right][START]
r_end = coins[right][END]
r_val = coins[right][VALUE]
r_win_size = (r_end-r_start) + 1
r_range_sum = r_win_size*r_val
cur_sum += r_range_sum # 3 + 6 ..
win_start_pos = r_end-k+1 # [0,1,2,3,4,5], ex: r_st=4 k=3 -> 4-3-1 => 2
# Remove out of range ranges
while coins[left][END] < win_start_pos:
l_start = coins[left][START]
l_end = coins[left][END]
l_val = coins[left][VALUE]
l_win_size = (l_end-l_start) + 1
l_range_sum = l_win_size*l_val
cur_sum -= l_range_sum
left += 1
# Partially covered ranges case
l_start = coins[left][START]
l_end = coins[left][END]
l_val = coins[left][VALUE]
uncovered_l_range_sum = 0
if l_start < win_start_pos:
l_uncovered_win_size = (win_start_pos-l_start)
uncovered_l_range_sum = l_uncovered_win_size*l_val
max_res = max(max_res, cur_sum-uncovered_l_range_sum)
return max_res % MOD
def calcu