mediumArraysPattern: Difference Array
Energy Grid Load Distribution Solution
Problem Statement
An energy grid consists of n power stations, indexed 0 to n-1, all initially providing 0 megawatts. You are given k load adjustment operations. Each operation [start, end, boost] adds 'boost' megawatts to every station in the range [start, end] inclusive. Let A[i] be the final output of station i after all operations. Let S[i] be the prefix sum of the grid, where S[i] = A[0] + A[1] + ... + A[i]. Your task is to calculate a transformation array T, where each index i stores T[i] = A[i] * S[i]. Return the array T.
Examples
Example 1:
Input:n = 4, operations = [[0, 2, 10], [1, 3, 5]]
Output:[100, 375, 600, 225]
Explanation: A = [10, 15, 15, 5]. S = [10, 25, 40, 45]. T[0]=10*10=100, T[1]=15*25=375, T[2]=15*40=600, T[3]=5*45=225.
Example 2:
Input:n = 3, operations = [[0, 1, 2], [2, 2, 10]]
Output:[4, 8, 140]
Explanation: A = [2, 2, 10]. S = [2, 4, 14]. T[0]=2*2=4, T[1]=2*4=8, T[2]=10*14=140.
Constraints
- 1 <= n <= 10^5
- 0 <= k <= 10^5
- 0 <= start <= end < n
- 1 <= boost <= 10^4
Time: O(n + k) Space: O(n)
Use a difference array to perform range updates in O(1) time, then compute the prefix sums to restore the station values in O(n). This reduces total complexity to O(n + k) by separating the logic of recording updates and calculating final states.
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
No solution code is currently loaded.
Complete this code in the workspace editor.