# O(log n) Problem 2 and O(n) Problem 3 solution

• Problem 2
Idea is to maintain first and last number of each round
at round t, the gap among consecutive numbers is pow(2, t-1)

``````int lastRemaining(int n) {
int base = 1, first = 1, last = n;
bool check_first = false;
while (first < last) { //remaining number is first, first + base, ..., last
base *= 2;
check_first = !check_first;
int r = (check_first?first:last) % base; //first (last) mod base cannot be r
if (first % base == r) first += base/2;
if (last % base == r) last -= base/2;
}
return first;
}
``````

Problem 3
Idea is to count occurrence of all corners of the sub-rectangles
The four corners of the large rectangles should appear once
Others may appear 2 or 4 times.

``````bool isRectangleCover(vector<vector<int>>& rectangles) {
unordered_map<int, unordered_map<int, int>> corner_count;
int minx = INT_MAX, maxx=INT_MIN, miny=INT_MAX, maxy=INT_MIN;
for (auto& rect : rectangles) {
minx = min(minx, rect[0]);
maxx = max(maxx, rect[2]);
miny = min(miny, rect[1]);
maxy = max(maxy, rect[3]);

corner_count[rect[0]][rect[1]]++;
corner_count[rect[2]][rect[1]]++;
corner_count[rect[0]][rect[3]]++;
corner_count[rect[2]][rect[3]]++;
}

for (auto itx = corner_count.begin(); itx != corner_count.end(); ++itx) {
int x = itx->first;
for (auto ity = itx->second.begin(); ity != itx->second.end(); ++ity) {
int y = ity->first;
int count = ity->second;
if ((x == minx || x == maxx) && (y == miny || y == maxy)) {
if ( count != 1 ) return false;
}
else {
if (count !=2 && count !=4) return false;
}
}
}
return true;
}
``````

• I think your code fails the following case:

``````[[1, 1, 2, 2], [2, 1, 3, 2],  [2, 1, 3, 2], [2, 1, 3, 2], [3, 1, 4, 2]]
``````

bool isRectangleCover(vector<vector<int>>& rectangles) {
unordered_map<int, unordered_map<int, int>> corner_count;
int minx = INT_MAX, maxx=INT_MIN, miny=INT_MAX, maxy=INT_MIN;
for (auto& rect : rectangles) {
minx = min(minx, rect[0]);
maxx = max(maxx, rect[2]);
miny = min(miny, rect[1]);
maxy = max(maxy, rect[3]);

``````    corner_count[rect[0]][rect[1]]++;
corner_count[rect[2]][rect[1]]++;
corner_count[rect[0]][rect[3]]++;
corner_count[rect[2]][rect[3]]++;
}

for (auto itx = corner_count.begin(); itx != corner_count.end(); ++itx) {
int x = itx->first;
for (auto ity = itx->second.begin(); ity != itx->second.end(); ++ity) {
int y = ity->first;
int count = ity->second;
if ((x == minx || x == maxx) && (y == miny || y == maxy)) {
if ( count != 1 ) return false;
}
else {
if (count !=2 && count !=4) return false;
}
}
}
return true;
``````

}

• @lzb700m I see. The code does not check for rectangles sharing top-left / top-right / bottom-left /bottom-right corners.
A naive solution would just be adding additional masks to each entry of the unordered_map to check whether the corner has been added as TL/TR/BL/BR...

The method is still O(n) as the mask is checked in O(1) time for each corner.

``````// pos encoding: 1 - TL 2- TR 4- BL 8-BR
// return false if a conflict in mask occurs (i.e. there used to be a rectangle with corner (x, y) at pos
inline bool insert_corner(unordered_map<int, unordered_map<int, int>>& corner_count, int x, int y, int pos) {
int& m = corner_count[x][y];
if (m & pos) return false;
m |= pos;
return true;
}

bool isRectangleCover(vector<vector<int>>& rectangles) {
// step 1: counting
unordered_map<int, unordered_map<int, int>> corner_count;
int minx = INT_MAX, maxx=INT_MIN, miny=INT_MAX, maxy=INT_MIN;
for (auto& rect : rectangles) {
minx = min(minx, rect[0]);
maxx = max(maxx, rect[2]);
miny = min(miny, rect[1]);
maxy = max(maxy, rect[3]);
if (!insert_corner(corner_count, rect[0], rect[1], 1)) return false;
if (!insert_corner(corner_count, rect[2], rect[1], 2)) return false;
if (!insert_corner(corner_count, rect[0], rect[3], 4)) return false;
if (!insert_corner(corner_count, rect[2], rect[3], 8)) return false;
}

//step2: checking
bool valid_corner[16] = {false};
bool valid_interior[16] = {false};

valid_corner[1] = valid_corner[2] = valid_corner[4] = valid_corner[8] = true;
valid_interior[3] = valid_interior[5] = valid_interior[10] = valid_interior[12] = valid_interior[15] = true;

for (auto itx = corner_count.begin(); itx != corner_count.end(); ++itx) {
int x = itx->first;
for (auto ity = itx->second.begin(); ity != itx->second.end(); ++ity) {
int y = ity->first;
if ((x == minx || x == maxx) && (y == miny || y == maxy)) {
if ( !valid_corner[mask] ) return false;
}
else {
return false;
}
}
}
}
return true;
}
``````

• I think your code fails the following case:
[[1, 1, 2, 2], [2, 1, 3, 2], [2, 1, 3, 2], [2, 1, 3, 2], [3, 1, 4, 2]]

Thanks, just added this test case.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.