This problem looks busy at first, but the accepted solution is built around one steady invariant. For 1589. Maximum Sum Obtained of Any Permutation, the solution in this repository is mainly a two pointers solution.
Guide
What?
Before optimizing anything, pin down what information is still useful after each move. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: two pointers, prefix sums, greedy.
The notes already sitting in the source point us in the right direction:
- Naive
- TLE
- 78 / 82 test cases passed.
Guide
When?
Reach for this shape when a direct simulation would work logically but waste time revisiting the same information. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are maxSumRangeQuery, counter, updateBIT, init, getSum.
Guide
Why?
The code is doing bookkeeping so your brain does not have to keep the entire search space open at once.
- Sorting is used to make local choices comparable, so the later scan does not have to rediscover order.
- The two-dimensional vector is the memory of the solution: grid state, DP state, or adjacency shape.
- The final return is not magic; it is the invariant after the loops or recursion have finished doing their accounting.
Guide
How?
Walk through the solution in this order:
- Start from the smallest reliable state.
- Expand one legal move at a time.
- Cache, count, or merge information as soon as it becomes settled.
- Let the final stored value answer the original question.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: O(n) to O(n log n), depending on the dominant loop or data structure operation
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01//Naive
02//TLE
03//78 / 82 test cases passed.
04class Solution {
05public:
06 int maxSumRangeQuery(vector<int>& nums, vector<vector<int>>& requests) {
07 int n = nums.size();
08
09 vector<int> counter(n, 0);
10
11 for(vector<int>& req : requests){
12 for(int pos = req[0]; pos <= req[1]; ++pos){
13 ++counter[pos];
14 }
15 }
16
17 sort(counter.begin(), counter.end());
18 sort(nums.begin(), nums.end());
19
20 long long ans = 0;
21 int MOD = 1e9 + 7;
22
23 for(int i = 0; i < n; ++i){
24 long long prod = (1LL * nums[i] * counter[i]) % MOD;
25 ans = (ans + prod) % MOD;
26 }
27
28 return ans;
29 }
30};
31
32//Binary indexed tree, Range Updates and Point Queries
33//Runtime: 864 ms, faster than 74.80% of C++ online submissions for Maximum Sum Obtained of Any Permutation.
34//Memory Usage: 98.3 MB, less than 55.20% of C++ online submissions for Maximum Sum Obtained of Any Permutation.
35//https://www.geeksforgeeks.org/binary-indexed-tree-range-updates-point-queries/
36//getElement -> getSum: now we the prefix sum of index i BITree[0...i] means arr[i]
37//updateBIT -> update: update BITree[l] and BITree[r-1] so range sum of arr[l...r] is updated
38class BIT{
39public:
40 int n;
41 vector<int> BITree;
42
43 void updateBIT(int index, int val)
44 {
45 // index in BITree[] is 1 more than the index in arr[]
46 index = index + 1;
47
48 // Traverse all ancestors and add 'val'
49 while (index <= n)
50 {
51 // Add 'val' to current node of BI Tree
52 BITree[index] += val;
53
54 // Update index to that of parent in update View
55 index += index & (-index);
56 }
57 }
58
59// // Constructs and returns a Binary Indexed Tree for given
60// // array of size n.
61// void init(vector<int>& arr, int n)
62// {
63// // Create and initialize BITree[] as 0
64// BITree = vector<int>(n+1, 0);
65
66// // Store the actual values in BITree[] using update()
67// for (int i=0; i<n; i++)
68// updateBIT(i, arr[i]);
69// }
70
71 BIT(int n){
72 this->n = n;
73 BITree = vector<int>(n+1, 0);
74 }
75
76 // SERVES THE PURPOSE OF getElement()
77 // Returns sum of arr[0..index]. This function assumes
78 // that the array is preprocessed and partial sums of
79 // array elements are stored in BITree[]
80 int getSum(int index)
81 {
82 int sum = 0; // Iniialize result
83
84 // index in BITree[] is 1 more than the index in arr[]
85 index = index + 1;
86
87 // Traverse ancestors of BITree[index]
88 while (index>0)
89 {
90 // Add current element of BITree to sum
91 sum += BITree[index];
92
93 // Move index to parent node in getSum View
94 index -= index & (-index);
95 }
96 return sum;
97 }
98
99 // Updates such that getElement() gets an increased
100 // value when queried from l to r.
101 void update(int l, int r, int val)
102 {
103 // Increase value at 'l' by 'val'
104 updateBIT(l, val);
105
106 // Decrease value at 'r+1' by 'val'
107 updateBIT(r+1, -val);
108 }
109};
110
111class Solution {
112public:
113 int maxSumRangeQuery(vector<int>& nums, vector<vector<int>>& requests) {
114 int n = nums.size();
115
116 vector<int> counter(n, 0);
117
118 BIT* bit = new BIT(n);
119
120 for(vector<int>& req : requests){
121 bit->update(req[0], req[1], 1);
122 }
123
124 for(int i = 0; i < n; ++i){
125 counter[i] = bit->getSum(i);
126 }
127
128 sort(counter.begin(), counter.end());
129 sort(nums.begin(), nums.end());
130
131 long long ans = 0;
132 int MOD = 1e9 + 7;
133
134 for(int i = 0; i < n; ++i){
135 long long prod = (1LL * nums[i] * counter[i]) % MOD;
136 ans = (ans + prod) % MOD;
137 }
138
139 return ans;
140 }
141};
142
143//line sweep
144//https://leetcode.com/problems/maximum-sum-obtained-of-any-permutation/discuss/854206/JavaC%2B%2BPython-Sweep-Line
145//Runtime: 1072 ms, faster than 49.11% of C++ online submissions for Maximum Sum Obtained of Any Permutation.
146//Memory Usage: 97 MB, less than 84.07% of C++ online submissions for Maximum Sum Obtained of Any Permutation.
147//time: O(NlogN), space: O(N)
148class Solution {
149public:
150 int maxSumRangeQuery(vector<int>& nums, vector<vector<int>>& requests) {
151 int n = nums.size();
152
153 vector<int> counter(n);
154
155 for(vector<int>& req : requests){
156 //freq of [req[0]...req[1]] is added by one,
157 ++counter[req[0]];
158 if(req[1]+1 < n) --counter[req[1]+1];
159 }
160
161 //convert the elements to their real freq
162 for(int i = 1; i < n; ++i){
163 counter[i] += counter[i-1];
164 }
165
166 sort(counter.begin(), counter.end());
167 sort(nums.begin(), nums.end());
168
169 long long ans = 0LL;
170 int MOD = 1e9+7;
171 for(int i = 0; i < n; ++i){
172 ans = (ans + 1LL*counter[i]*nums[i]) % MOD;
173 }
174
175 return ans;
176 }
177};Cost
Complexity
Time
O(n) to O(n log n), depending on the dominant loop or data structure operation
Dominated by the main traversal, recursion, or data-structure operations in the code.
Space
O(n) in the usual case for auxiliary containers or recursion
Auxiliary state plus the answer structure where the problem requires one.