This is one of those problems where the clean idea matters more than the amount of code. For 850. Rectangle Area II, the solution in this repository is mainly a binary search solution.
Guide
What?
The first job is to translate the English prompt into state, transition, and stopping conditions. 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: binary search, two pointers, greedy.
The notes already sitting in the source point us in the right direction:
- Approach #1: Principle of Inclusion-Exclusion
- TLE
- 46 / 76 test cases passed.
- time: O(N*2^N), space: O(N)
Guide
When?
This is the kind of solution you want when the problem has structure hiding inside a messy-looking input. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are intersect, rectangleArea, imapx, imapy, getRangeMid.
Guide
Why?
The point of the implementation is not to make the code longer. It is to avoid doing the same thinking twice.
- Sorting is used to make local choices comparable, so the later scan does not have to rediscover order.
- A map keeps the lookup side cheap; the code pays a little memory to avoid repeated searching.
- A set is doing the membership or uniqueness work, which keeps the main loop readable.
- The two-dimensional vector is the memory of the solution: grid state, DP state, or adjacency shape.
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^3), space: O(N^2)
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01//Approach #1: Principle of Inclusion-Exclusion
02//TLE
03//46 / 76 test cases passed.
04//time: O(N*2^N), space: O(N)
05class Solution {
06public:
07 vector<int> intersect(vector<int>& rec1, vector<int>& rec2){
08 //the returned rectangle will have negative side if the two input rectangles have no intersection
09 return {max(rec1[0], rec2[0]),
10 max(rec1[1], rec2[1]),
11 min(rec1[2], rec2[2]),
12 min(rec1[3], rec2[3])};
13 };
14
15 long area(vector<int>& rec){
16 long dx = max(rec[2] - rec[0], 0);
17 long dy = max(rec[3] - rec[1], 0);
18 return dx*dy;
19 }
20
21 int rectangleArea(vector<vector<int>>& rectangles) {
22 int n = rectangles.size();
23
24 long ans = 0;
25 for(int subset = 1; subset < (1<<n); subset++){
26 //subset from 0001 to 1111
27 //maximum possible rectangle
28 vector<int> rec = {0, 0, (int)1e9, (int)1e9};
29 int parity = -1;
30 //inspect the subset, start from least significant bit
31 for(int bit = 0; bit < n; bit++){
32 if((subset>>bit) & 1){
33 rec = intersect(rec, rectangles[bit]);
34 parity *= -1;
35 }
36 }
37 /*
38 if there are odd set bits, parity is 1
39 otherwise parity is -1
40 */
41 ans += parity * area(rec);
42 }
43
44 long mod = 1e9+7;
45 ans %= mod;
46
47 //?
48 if(ans < 0) ans += mod;
49 return ans;
50 }
51};
52
53//Approach #2: Coordinate Compression
54//Runtime: 196 ms, faster than 6.10% of C++ online submissions for Rectangle Area II.
55//Memory Usage: 8.3 MB, less than 100.00% of C++ online submissions for Rectangle Area II.
56//time: O(N^3), space: O(N^2)
57class Solution {
58public:
59 int rectangleArea(vector<vector<int>>& rectangles) {
60 int n = rectangles.size();
61 set<int> xvals, yvals;
62
63 for(vector<int>& rec : rectangles){
64 xvals.insert(rec[0]);
65 yvals.insert(rec[1]);
66 xvals.insert(rec[2]);
67 yvals.insert(rec[3]);
68 }
69
70 vector<int> imapx(xvals.begin(), xvals.end());
71 vector<int> imapy(yvals.begin(), yvals.end());
72 sort(imapx.begin(), imapx.end());
73 sort(imapy.begin(), imapy.end());
74
75 map<int, int> mapx, mapy;
76 // cout << "imapx: " << endl;
77 for(int i = 0; i < imapx.size(); i++){
78 mapx[imapx[i]] = i;
79 // cout << i << " " << imapx[i] << endl;
80 }
81 // cout << "imapy: " << endl;
82 for(int i = 0; i < imapy.size(); i++){
83 mapy[imapy[i]] = i;
84 // cout << i << " " << imapy[i] << endl;
85 }
86
87 vector<vector<bool>> grid = vector(imapx.size(), vector(imapy.size(), false));
88 for(vector<int>& rec : rectangles){
89 //fill the corresponding grids
90 for(int x = mapx[rec[0]]; x < mapx[rec[2]]; x++){
91 for(int y = mapy[rec[1]]; y < mapy[rec[3]]; y++){
92 grid[x][y] = true;
93 }
94 }
95 }
96
97 long ans = 0;
98
99 for(int x = 0; x < grid.size(); x++){
100 for(int y = 0; y < grid[0].size(); y++){
101 if(grid[x][y]){
102 ans += (long)(imapx[x+1] - imapx[x]) * (imapy[y+1] - imapy[y]) % ((int)1e9+7);
103 ans %= ((int)1e9+7);
104 }
105 }
106 }
107
108 ans %= ((int)1e9+7);
109
110 return ans;
111 }
112};
113
114//Approach #3: Line Sweep
115//Runtime: 16 ms, faster than 43.29% of C++ online submissions for Rectangle Area II.
116//Memory Usage: 7.1 MB, less than 100.00% of C++ online submissions for Rectangle Area II.
117//time: O(N^2* logN), space: O(N^2)
118class Solution {
119public:
120 int rectangleArea(vector<vector<int>>& rectangles) {
121 int OPEN = 0, CLOSE = 1;
122 int n = rectangles.size();
123 //every rectangle form two events
124 vector<vector<int>> events(n*2);
125
126 int i = 0;
127 for(vector<int>& rec : rectangles){
128 //horizontal line(y-coordinate), open or close, x1, x2
129 events[i++] = {rec[1], OPEN, rec[0], rec[2]};
130 events[i++] = {rec[3], CLOSE, rec[0], rec[2]};
131 }
132 //sort by y
133 sort(events.begin(), events.end(),
134 [](vector<int>& a, vector<int>& b){
135 return a[0] < b[0];
136 });
137
138 //actives: vector of (x1,x2), currently opening events
139 vector<vector<int>> actives;
140 int last_y = events[0][0];
141 long ans = 0;
142 for(vector<int>& event : events){
143 int y = event[0];
144 bool isClose = event[1];
145 int x1 = event[2], x2 = event[3];
146
147 /*
148 query: on current horizontal line,
149 the length of intervals formed by active events
150 */
151 long query = 0;
152 int cur = INT_MIN;
153 // cout << "y: [" << last_y << ", " << y << "]" << endl;
154 for(vector<int>& active : actives){
155 cur = max(cur, active[0]);
156 // cout << "x: [" << active[0] << ", " << active[1] << "], cur: " << cur << ", width: " << max(active[1] - cur, 0) << endl;
157 /*
158 cur: last right boundary,
159 since rectangles may overlap,
160 so we need the max()
161 */
162 query += max(active[1] - cur, 0);
163 cur = max(cur, active[1]);
164 }
165
166 // cout << "width: " << query << ", height: " << y - last_y << endl;
167 /*
168 query: the total length in horizontal direction
169 y - last_y: the height of current rectangle
170 */
171 ans += query * (y - last_y);
172
173 //update actives(current open events)
174 if(!isClose){
175 actives.push_back({x1, x2});
176 sort(actives.begin(), actives.end(),
177 [](vector<int>& a, vector<int>& b){
178 return a[0] < b[0];
179 });
180 }else{
181 //find out the corresponding open active event and erase it
182 for(auto it = actives.begin(); it != actives.end(); it++){
183 if((*it)[0] == x1 && (*it)[1] == x2){
184 actives.erase(it);
185 break;
186 }
187 }
188 }
189
190 // cout << "actives: ";
191 // for(auto it = actives.begin(); it != actives.end(); it++){
192 // cout << (*it)[0] << ", " << (*it)[1] << " | ";
193 // }
194 // cout << endl;
195
196 last_y = y;
197 }
198
199 ans %= (int)1e9+7;
200 return ans;
201 }
202};
203
204//Approach #4: Segment Tree
205//Runtime: 24 ms, faster than 26.22% of C++ online submissions for Rectangle Area II.
206//Memory Usage: 20.8 MB, less than 25.00% of C++ online submissions for Rectangle Area II.
207//time: O(N* logN), space: O(N)
208class Node {
209public:
210 int start, end;
211 vector<int> X;
212 Node *left, *right;
213 int count;
214 long total;
215
216 Node(int start, int end, vector<int> X){
217 this->start = start;
218 this->end = end;
219 this->X = X;
220 left = nullptr;
221 right = nullptr;
222 count = 0;
223 total = 0;
224 }
225
226 int getRangeMid(){
227 return start + (end-start)/2;
228 }
229
230 Node* getLeft(){
231 if(left == nullptr) left = new Node(start, getRangeMid(), X);
232 return left;
233 }
234
235 Node* getRight(){
236 if(right == nullptr) right = new Node(getRangeMid(), end, X);
237 return right;
238 }
239
240 long update(int i, int j, int val){
241 if(i >= j) return 0;
242 if(start == i && end == j){
243 count += val;
244 }else{
245 getLeft()->update(i, min(getRangeMid(), j), val);
246 getRight()->update(max(getRangeMid(), i), j, val);
247 }
248
249 if(count > 0) total = X[end] - X[start];
250 else total = getLeft()->total + getRight()->total;
251
252 return total;
253 }
254};
255
256class Solution {
257public:
258 int rectangleArea(vector<vector<int>>& rectangles) {
259 int OPEN = 1, CLOSE = -1;
260 int n = rectangles.size();
261 vector<vector<int>> events(n*2);
262 set<int> xvals_set;
263
264 int i = 0;
265 for(vector<int>& rec : rectangles){
266 //horizontal line, open or close, x1, x2
267 events[i++] = {rec[1], OPEN, rec[0], rec[2]};
268 events[i++] = {rec[3], CLOSE, rec[0], rec[2]};
269 xvals_set.insert(rec[0]);
270 xvals_set.insert(rec[2]);
271 }
272 //sort by y
273 sort(events.begin(), events.end(),
274 [](vector<int>& a, vector<int>& b){
275 return a[0] < b[0];
276 });
277
278 vector<int> xvals(xvals_set.begin(), xvals_set.end());
279 sort(xvals.begin(), xvals.end());
280
281 map<int, int> rxvals;
282 for(int i = 0; i < xvals.size(); i++){
283 rxvals[xvals[i]] = i;
284 }
285
286 int last_y = events[0][0];
287 long ans = 0;
288 long cur_x_sum = 0;
289 Node active(0, xvals.size()-1, xvals);
290
291 for(vector<int>& event : events){
292 int y = event[0];
293 int type = event[1];
294 int x1 = event[2], x2 = event[3];
295
296 ans += cur_x_sum * (y - last_y);
297 cur_x_sum = active.update(rxvals[x1], rxvals[x2], type);
298 last_y = y;
299 }
300
301 ans %= (int)1e9+7;
302 return ans;
303 }
304};Cost
Complexity
Time
O(N^3), space: O(N^2)
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.