Assume you have an array of length n initialized with all 0's and are given k update operations.
Each operation is represented as a triplet: [startIndex, endIndex, inc] which increments each element of subarray A[startIndex ... endIndex](inclusive) with inc.
Return the modified array after all k operations were executed.
Example
A = [0, 0, 0, 0, 0]
Update:
[1,3,2] => A = [0, 2, 2, 2, 0]
[2,4,3] => A = [0, 2, 5, 5, 3]
[0,2,-2] => A = [-2,0, 3, 5, 3]
Result = [-2,0, 3, 5, 3]
Solution
- The straightforward solution would be for each update query (start, end, k) we for from start -> end and update a[i] += k.
Runtime: O(m*n) (m: number of query, n: A.size())
- A better way is to utilize the prefix sum: S[i] = sum(A[0]...A[i]), S[i] will have information of subarray A[0..i].
For each query (start, end, k), we update:
- A[start] += k. So when calculate S[i] (i >= start), all S[i] will be added k.
- Because we only want to add up to end item, we have to update A[end+1] -= k so when calculate S[i] (i > end),k is subtracted from all S[i].
vector<int> getModifiedArray(int length, vector<vector<int>>& updates) {
vector<int> a = vector<int>(length, 0);
for(auto update: updates) {
int u = update[0];
int v = update[1];
int val = update[2];
a[u]+=val;
if (v+1 < length) a[v+1]-=val;
}
for(int i = 1; i < length; i++)
a[i] += a[i-1];
return a;
}
Runtime: O(m + n)
Application
- https://leetcode.com/problems/meeting-rooms-ii/
We can think of this problem as follow: let time[i]: number of meeting at time i, for each meeting [start, end], we add 1 to time[i], where start <= i < end. The problem become, find max(time[i]) after we update for all meetings. Now we can apply the abobe technique for solving this problem, just use a map<int, int> instead of an array, because the array need to be update now is a continuous range (time), not a concrete array.
int minMeetingRooms(vector<vector<int>>& intervals) {
sort(intervals.begin(), intervals.end(), [](vector<int> x, vector<int> y) {
return x[0] < y[0];
});
map<int, int> a;
for(auto meeting: intervals) {
int s = meeting[0];
int e = meeting[1];
a[s]++;
a[e]--;
}
int count = 0;
int res = 0;
for(auto pair: a) {
count += pair.second;
res = max(res, count);
}
return res;
}
Runtime: O(2n*log(2n))
Simillaly, we can do following problems:
2.https://leetcode.com/problems/my-calendar-ii
3.https://leetcode.com/problems/my-calendar-iii