Plane Sweep To Solve a hard Google Onsite Problem @08/10

• Yesterday, I meet a hard problem on Google onsite, of course, I do not finished to solve it in the limited time, I am really depressed as most of my classmates are asked to solve some much more easy problem set.

So let us check the problem directly ....

Given N rectangle in the plane, how to check whether all the rectangle can form a big rectangle exactly !

To make it clear, the interviewer mean that all the matrix should have no gap in between and no overlap to form a big rectangle !

At the first glance, I just think a brute force solution to sweep from the left most edge to the most right edge and check whether along all the edges we can fill the big rectangle exactly !. ... So finally, my method is a little messy, I just can not implement elegently....So you know what happened next ...... Goodbye, Google.....

Let us first check out a easy solution :

We can just calculate all the rectangle area, and check whether the overall area equal the most outer rectangle area. Then we just need to check whether there exists 2 rectangle interact in the plane !

Here is basic implementation by myself ....

``````struct Rect {
int x0, x1, y0, y1;
};

class Solution {
bool rect_overlap(Rect& a, Rect& b) {
if (a.x0 > b.y0 || b.x0 > a.y0) { return false; }
if (a.y0 > b.y1 || b.y0 < a.y1) { return false; }
return true;
}

int rect_area(Rect &a) {
return (y1 - y0) * (x1 - x0);
}

bool rect_check(vector<Rect> &rects) {
int n = rects.size();
long long sum_area = 0;
int xx0 = rects[0].x0, yy0 = rects[0].y0;
int xx1 = rects[1].x1, yy1 = rects[0].y1;
for (int i = 0; i < n; i++) {
xx0 = min(rects[i].x0, xx0);
yy0 = min(rects[i].y0, yy0);
xx1 = max(rects[i].x1, xx1);
yy1 = max(rects[i].y1, yy1);
sum_area += rect_area(rects[i]);
for (int j = i + 1; j < n; j++) {
if (rect_overlap(rects[i], rects[j])) {
return false;
}
}
}
return sum_area == (xx1 - xx0) * (yy1 - yy0);
}
};
``````

Hehe, of course this time complexicity is O(N^2) ! But we want O(NlogN) ....*

Let us change the orginal problem into a new problem :

Problem Def :

Given N rectangle in the plane, how to check whether there are 2 rectangle overlap in NlogN time cost

To solve this problem, I strong recommend you to refer the post by a Chinese guy

The main ideas is to use the plane swap ideas to solve the problem !

We will split the plane along all the edges of the rectangle and swap all the lines from left to right !

I will not delve into the details, just give you the template to know the key ideas behind the problem ...

``````class SegmentTree {
void  Init() ;
void  Insert(int  left , int  right);
void  Delete(int  left , int  right);
void  hasIntersect(int  left , int  right);
};

class Solution {
boolean has_rectangle_intersect(rectangle r[] , int n) {
map all the {r[0].left_x , r[0].right_x , ... ,
r[n-1].left_x , r[n-1].right_x} to the mapx[] ;
for( i = 0 ; i < n ; ++ i){
event[i<<1]     = {r[i].left_x , r[i].down_y , r[i].up_y , +1 } ;
event[(i<<1)|1] = {r[i].right_x, r[i].down_y , r[i].up_y , -1 } ;
}
sort event[0..2*n-1] based on x in increasing order
tree.init() ;
for( i = 0 ; i < n<<1 ; ++ i){
if( event[i] is insert event){
if( tree.hasIntersection(event[i].down_y , event[i].up_y) )
return true ;
tree.Insert(event[i].down_y , event[i].up_y) ;
}else{
tree.Delete(event[i].down_y , event[i].up_y);
}
}
return false ;
}
};

``````

• @fight-for-dream
This is really a hard problem. Thanks so much for sharing!
I'm thinking: what if the rectangles are not fixed on the plane, but rather they can move?
Then the question becomes: given N rectangles, is it possible to position them to form a larger rectangle? - I have no clue how to solve this one...

• can we just make a hashset which contains all the previous points? ie we traverse each rectangle and add all its point to the hashset. we then move on to the next one and if ever reach a point thats already in the hashset then we can stop.

• @alan28
Sorry I didn't get it - if the rectangles can move, each rectangle should be represented by (w, h) instead of points with x/y values. Please correct me if I was wrong.

• @alan28 how would that work if your rectangles are large? your running time and space could be arbitrarily bad, regardless of the number of rectangles in the input.

• This is different from OP's solution. OP checks whether N rectangles have any intersection, while I avoid all geometric tests. I sweep from left to right and check that left-hand boundaries of rectangles match up with right-hand boundaries of rectangles. It's also O(n log n).

Given N rectangles with integer coordinates, check whether they are an exact
cover of a rectangle

If you don't know already, Google's on-site interview process involves 5
independent interviews in one day. In each one a Google Software Engineer poses
a problem that should be solved in 45 min to 1 hr. The interviewee can code on a
white board or in Google Docs (check with your recruiter for details) in a
language of their choice, but not pseudo-code.

By itself, the question is not all that intimidating, but the time-limit can
make it quite challenging. That's why I'm practising!

As usual, there is a fairly straightforward "brute force" solution, and some
better solutions. I'll give hints and solutions immediately after the jump so
avoid spoilers by not looking past the example inputs yet.

Hint 1

Try to find a brute-force solution by looking at the total area of the rectangles.

Hint 2

After computing the area, can you avoid comparing every pair of rectangles?

Hint 3

The problem can be solved in O(N log N), both with and without computing areas.

Hint 4

What needs to occur at every left-hand segment of an input rectangle that is
interior to the smallest rectangle that bounds the input rectangles? At every
right-hand segment? At the vertical segments not interior?

Solutions from area

One solution is to compute the area of the smallest bounding rectangle, and the
combined areas of the N input rectangles. The input data is unsorted, so you
need to do an O(N) scan of the input to find the minimum and maximum points,
both vertically and horizontally (up to 4 points). If the areas differ, output
False, and if they are the same, you need to check that no pair of input
rectangles intersect. To see why, look at the input below.

Testing whether a pair of rectangles intersect is
a simple, O(1) calculation
(though I would understand if you failed to get it onto the whiteboard in 5
minutes under pressure), so we know we can finish in O(N^2) time by comparing (N
choose 2) pairs of input rectangles.

Some light reading suggests that the intersections can be tested in O(N log N)
time in some cases, but the solutions seem far from simple. I didn't look at
this very deeply, but for further reading:

I'll now present a solution that does not require any 2D geometric tests.

My Solution

Imagine, first, that the (smallest) rectangle bounding the inputs is a cylinder,
so that its leftmost edge coincides with its rightmost edge. Now we can state
the 'algorithm' in one sentence:

If **(P) every point interior to a right-hand edge of an input rectangle is unique,
and it coincides with a point of a left-hand edge of an input rectangle, and
vise versa **, then we (Q) output True, and otherwise we output False.

Take a moment to let that sink in. We are claiming that P if and only if Q. Let
us make clear here that when we say rectangles intersect, we mean that their
interiors intersect. The explanation is a bit dense, but hopefully you'll come
to the same conclusions by making some drawings.

If P is false, then one of two things can happen. If points interior to the
right-hand edges of two distinct rectangles coincide, then the rectangles
intersect. Otherwise, without loss of generality, we may assume there is there
is some point `p` on a left-hand edge of an input rectangle, call it `A`, that
does not coincide with a point on a right-hand edge of an input rectangle. Thus,
`p` is interior to a small open disc that both contains points interior to `A`
and points exterior to `A`. The same disc is either entirely inside a rectangle
distinct from `A`, which will necessarily intersect with `A`, or it contains
points exterior to all rectangles distinct from `A`, and thus contains a hole in
the bounding cylinder. Thus we output False, so Q is false.

If Q is false, on the other hand, then either two distinct rectangles intersect,
or a point in the bounding cylinder falls outside of all input rectangles. If
rectangles intersect and they have intersecting vertical segments, then P is
false, so we may assume that is not the case. But then, the vertical segment of
one rectangle must be interior to another rectangle, which again falsifies P.
Finally, if a point falls outside of all rectangles, then there are vertical
segments to its left and right that falsify P.

Thus, we have shown that P is a necessary and sufficient condition for the N
rectangles to be an exact cover of a rectangle, q.e.d.

Now we need to code the solution. The short of it is, we sort a copy of the
input rectangles by left-edge x-coordinates, and we sort another copy by
right-edge x-coordinates. The first left edge and last right edge are special
cases, but are easily dealt with. We then process the vertical segments in the
sorted lists, at each x-coordinate, and simply compare the lists.

The bottleneck in time-complexity is in sorting the inputs, plus we need O(N)
space to make left-edge-sorted and right-edge-sorted copies of the inputs.

I am assuming that an input rectangle is given as a bottom-left point and a
top-right point; for example, a unit square is `[[1,1],[2,2]]`.

A final word of warning before you delve into my Python code. I am primarily a
C-programmer leveraging some features of Python, so my code is not very
"Pythonic". Suggestions, improvements, and more test cases welcome.

``````def isBigRect(rectangles):
if rectangles==[]:
return True
L=processBoundaries(rectangles,leftOrRight='left')
R=processBoundaries(rectangles,leftOrRight='right')
if L==False or R==False or not len(L)==len(R):
return False
L[-1][0]=R[-1][0]
R[0][0]=L[0][0]
if not L==R:
return False
else:
return True

def processBoundaries(B,leftOrRight='left'):
x0orx1=0
if leftOrRight=='right':
x0orx1=1
res=[[]]
elif leftOrRight=='left':
x0orx1=0
res=[]
else:
print 'process boundaries input error'
return False
B=[ [x[x0orx1][0],[x[0][1],x[1][1]]] for x in B]
B.sort(cmp=lambda x,y: x[0]-y[0])
i=0
while i<len(B):
x=B[i][0]
res.append( [x,[]] )
while i<len(B) and B[i][0]==x:
res[-1][1].append(B[i][1])
i=i+1
res[-1][1]=mergeSpecialIntervals(res[-1][1])
if res[-1][1]==False:
return False
if leftOrRight=='right':
res[0]=['first',res[-1][1]]
else:
res.append(['last',res[0][1]])
return res

def mergeSpecialIntervals(L):
if L==[]:
return False
if len(L)==1:
return L
L.sort(cmp=lambda x,y: x[0]-y[0])
res=[L[0]]
for i in range(len(L)-1):
if L[i][1]>L[i+1][0]:
return False
elif L[i][1]==L[i+1][0]:
res[-1][1]=L[i+1][1]
i=i+2
else:
res.append(L[i])
i=i+1
if i == len(L)-1:
res.append(L[i])
return res

A=[[[[0,0],[4,1]],
[[7,0],[8,2]],
[[6,2],[8,3]],
[[5,1],[6,3]],
[[4,0],[5,1]],
[[6,0],[7,2]],
[[4,2],[5,3]],
[[2,1],[4,3]],
[[0,1],[2,2]],
[[0,2],[2,3]],
[[4,1],[5,2]],
[[5,0],[6,1]]],

#shuffled the above a little
[[[0,0],[4,1]],
[[7,0],[8,2]],
[[5,1],[6,3]],
[[6,0],[7,2]],
[[4,0],[5,1]],
[[4,2],[5,3]],
[[2,1],[4,3]],
[[0,2],[2,3]],
[[0,1],[2,2]],
[[6,2],[8,3]],
[[5,0],[6,1]],
[[4,1],[5,2]]],

[[[0,0],[4,1]]],

[],

#vertical stack
[[[0,0],[1,1]],
[[0,1],[1,2]],
[[0,2],[1,3]],
[[0,3],[1,4]],],

#horizontal stack
[[[0,0],[1,1]],
[[1,0],[2,1]],
[[2,0],[3,1]],
[[3,0],[4,1]],],

]

print 'should be True'
for a in A:
print isBigRect(a)

B=[
#missing a square
[[[0,0],[4,1]],
[[7,0],[8,2]],
[[6,2],[8,3]],
[[5,1],[6,3]],
[[6,0],[7,2]],
[[4,2],[5,3]],
[[2,1],[4,3]],
[[0,1],[2,2]],
[[0,2],[2,3]],
[[4,1],[5,2]],
[[5,0],[6,1]]],

#exceeds top boundary
[[[0,0],[4,1]],
[[7,0],[8,2]],
[[5,1],[6,4]],
[[6,0],[7,2]],
[[4,0],[5,1]],
[[4,2],[5,3]],
[[2,1],[4,3]],
[[0,2],[2,3]],
[[0,1],[2,2]],
[[6,2],[8,3]],
[[5,0],[6,1]],
[[4,1],[5,2]]],

#two overlapping rectangles
[[[0,0],[4,1]],
[[0,0],[4,1]]],

#exceeds right boundary
[[[0,0],[4,1]],
[[7,0],[8,3]],
[[5,1],[6,3]],
[[6,0],[7,2]],
[[4,0],[5,1]],
[[4,2],[5,3]],
[[2,1],[4,3]],
[[0,2],[2,3]],
[[0,1],[2,2]],
[[6,2],[8,3]],
[[5,0],[6,1]],
[[4,1],[5,2]]],

# has an intersecting pair
[[[0,0],[5,1]],
[[7,0],[8,2]],
[[5,1],[6,3]],
[[6,0],[7,2]],
[[4,0],[5,1]],
[[4,2],[5,3]],
[[2,1],[4,3]],
[[0,2],[2,3]],
[[0,1],[2,2]],
[[6,2],[8,3]],
[[5,0],[6,1]],
[[4,1],[5,2]]],

#skips column 4
[[[0,0],[4,1]],
[[7,0],[8,2]],
[[5,1],[6,3]],
[[6,0],[7,2]],
[[2,1],[4,3]],
[[0,2],[2,3]],
[[0,1],[2,2]],
[[6,2],[8,3]],
[[5,0],[6,1]],],

#exceed left boundary
[[[0,0],[4,1]],
[[7,0],[8,2]],
[[5,1],[6,3]],
[[6,0],[7,2]],
[[4,0],[5,1]],
[[4,2],[5,3]],
[[2,1],[4,3]],
[[-1,2],[2,3]],
[[0,1],[2,2]],
[[6,2],[8,3]],
[[5,0],[6,1]],
[[4,1],[5,2]]],

#horizontal stack with overlapping left boundaries at x=1
[[[0,0],[1,1]],
[[1,0],[2,1]],
[[1,0],[3,1]],
[[3,0],[4,1]],],
]

print 'should be False'
for b in B:
print isBigRect(b)
``````

• @fight.for.dream Can you explain the n-rectangles intersection solution in O(n log n)? I have looked around and it doesn't look that simple. I doubt they expected you to code this.

• @StefanPochmann
Do you have any good idea for this question?

• @alejandroerickson Nice idea by you. As for @fight.for.dream's, I think a segment tree is overkill. Because we don't need to support overlapping segments here, as we can simply `return false` when we detect an overlap. So we can just use a C++ `set` of intervals or a `map` mapping interval starts to interval ends or lengths.

• would it be possible to share in which office you did the interview? thanks!

• Every rectangle would have two intervals (y1,y2) on y axis and (x1, x2) on x axis. We need to sort all the y coordinates first based on this intervals and then x coordinates based on this interval.

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