ORIGINAL CODING QUESTION
Peak load after batch updates
Start with n zero-valued slots. Each update adds a nonnegative amount to every slot in the inclusive range [left,right]. Return the largest final slot value.
Original exercise · medium. Editorial role relevance does not imply a company has asked this question.
Input and output
n m, then m triples (left,right,amount), zero-based.
Constraints
1 ≤ n ≤ 10000; 0 ≤ m ≤ 1000; 0 ≤ left ≤ right < n; amount in [0,1000].
Example 1
Input
4 2 0 2 3 1 3 4
Output
7
The middle slots reach 7.
Example 2
Input
3 0
Output
0
Without updates, peak load is zero.
Explain your approach
Explain your time and auxiliary space complexity. Which input makes your algorithm work hardest?
Private grading inputs, expected outputs and canonical reference implementations are withheld. Authored expected outputs were cross-checked with independent reference oracles; compiler/runtime behavior still needs a verified execution provider.
Hint 1
Only boundaries need individual changes.
Hint 2
Add at left and subtract after right.
Hint 3
Take the maximum prefix sum.
Practice this question
Save your work privately, explain decisions and return to your revision queue.
Open practice workspaceBrowse the question library →