Take the 2-minute tour ×

Let's say I have an array of objects called Point.
Point object has x and y values.

To make it more difficult, let's say there are no initial boundaries which means the rectangular area we want to find are bounded by Point objects. So, there are at least 4 Point objects.

so if the array only has 4 Point objects: Point(0,0), Point(100,0) Point(0,100) and Point(100,100), we want to return 100*100, the rectangular area.

This is easy part. But think about situation where there are more than 4 Point objects. How do you find the maximum rectangular area?

public int maxArea(Point[] points)
    int area;
    //do algo
    return area;

EDIT: Just by looking at the min and max of y and x doesn't guarantee because im looking for the rectangular area that are free of Point objects. so there is nothing inside that maximum rectangle area

share|improve this question
Max area? Infinite? –  quasiverse Oct 20 '12 at 2:58
max area that are bounded by Point objects. With Point(0,0), Point(100,0) Point(0,100) and Point(100,100), i said its 100*100 so its not infinite... –  ealeon Oct 20 '12 at 3:00
... what do you mean by bounded? Suppose you have (0,0), (0,100), (100,0), (100,100), (50,50), What's the max rectangle? –  quasiverse Oct 20 '12 at 3:01
Is the rectangle supposed to be parallel to the axis? or can be angled? –  st0le Oct 20 '12 at 4:47
@ealeon, are you planning to accept/tick/mark an answer this time? –  Alexander Oct 20 '12 at 16:28

4 Answers 4

up vote 2 down vote accepted

Let me first formulate the problem as I believe it was meant:

  • The rectangle to be found has horizontal (constant y) and vertical (constant x) borders, i.e. no "rotations".

  • The rectangle has at least one point on the 'internal' ('open') part of each of its edges, i.e. not at a corner. (it may have more than one point on any edge, and ALSO points at its corners.) This rules out the 'infinite' solutions, because all points have finite x,y. It also rules out the cases where we might intend to define the rectangle by only TopLeft and BottomRight points and similar constructs.

  • we look for the rectangle with the maximum area among all that satisfy the above conditions.

Assuming the above to be a correct (re)formulation of the problem, I believe that it is a two-dimensional optimization problem with potentially many 'local' optima. Any approach of the type "start at something and gradually improve" will only find the local optimum, but not necessarily the global one.

I have not been able to come up with something better than a O(N^2) approach, involving - roughly speaking - N times a local optimization, where each local optimization is O(N). I'll sketch the method with some code snippets (partially pseudo-code or remarks) for the essential part of the local optimization. The remainder is "more of the same" and should not be difficult to fill in.

To cut down on wording without becoming inaccurate, henceforth I will mean by "a point on the edge (of a recctangle)" a point that is on the 'inner' part of the edge, not at a corner. Likewise, by 'rectangle' I will mean an "eligible" reactangle, i.e. one that satisfies the basic conditions: no points inside, and at least one point on each of its edges.

Now, the LOCAL optimization is "defined" by a specific point from the points-set, in combination with a specific "border-type" from {Left, Top, Right, Bottom}. Assume that we have chosen a point L and border-type "Left"; The locally optimal solution is defined as the 'best" (largest area) rectangle that has L on its Left edge.

We're going to construct all (L,Left)-rectangles and keep track of the largest one that we find on the way.

Observe: any (L,Left)-rectangle that has point R on its right border, must have a point T on its Top border and a point B on its bottomm border, where

L.x < T.x < R.x
L.x < B.X < R.X
B.y < L.y < T.y
B.y < R.y < T.Y

Image now, that we scan the points in x-ordered fashion, starting after L.

At the one hand: before we can find R, the above conditions show that we must first encounter T and B.

At the other hand, as soon as we've found R, from all the points with y > L.y that we've encountered in-between, we will by now be bounded by the one with the lowest y. and likewise for the bottom-border.

With N the number of points {P}, Let index_X[] be the array of indices for the x-sorted points, such that P[index_X[i]]x <= P[index_X[j]].x whenever i is less than j.

Furthermore, let iL be the index of L in the x-sorted array: P[index_X[iL]] = L.

In the following code-snippets (VB-syntax; it shouldn't be too difficult to translate in whatever language you use), we first determine "some" T (a top-edge point) and "some" B (a bottom-edge point). Then, we keep scanning, and whenever we find a point R that completes a rectangle, we: (a) calculate the area to update the optimum if it is larger; (b) replace T or B by the found R (depending on whether R is above L or below), and repeat the search for R.

    Dim indx As Integer = iL + 1 'first point to consider on the right of L
    Dim T As PointF = Nothing
    Dim B As PointF = Nothing
    ' find T,B
    While (indx < N AndAlso (T = Nothing OrElse B = Nothing))

      Dim Q As PointF = Pts(indx_X(indx))

      If (Q.Y > L.Y) Then
        ' a candidate for T
        If (T = Nothing) OrElse (Q.Y < T.Y) Then
          T = Q
        End If

      ElseIf (Q.Y < L.Y) Then
        ' a candidate for B
        If (B = Nothing) OrElse (Q.Y > B.Y) Then
          B = Q
        End If

        Return -1 'Failure for L altogether: Q has exactly the same y-value as L and we didn't find yet both T and B.
      End If

      indx += 1
    End While

    If (T = Nothing OrElse B = Nothing) Then
      Return -1  'Failure for L: we have exhausted all points on the right without finding both T and B.
    End If

    ' we have "some" T and B, now proceed to find all (L,Left) rectangles
    ' intialize result (= max area from (L,Left)-rectangles).
    Dim result As Double = -1
    ' the next point to consider
    indx += 1
    ' find successive rectangles, by searching for R, given L (fixed) and T,B (occasionally updated). 
    While (indx < N)

      Dim R As PointF = Pts(indx_X(indx)) 'candidate

      If (R.Y = L.Y) Then
        ' rectangle found, process it.
        Dim area As Double = (R.X - L.X) * (T.Y - B.Y)
        If area > result Then
          result = area
        End If
        ' it all stops here: no further rectangles {L,Left) are possible as they would have this R inside.
        Exit While
      End If

      If (R.Y > L.Y) Then
        ' a point with y > L.Y:
        ' if it is above T we can ignore it.
        ' if is below T, it is the R-bound for the rectangle bounded by L,T,B
        If (R.Y < T.Y) Then
          ' process the rectangle
          If area > result Then
            result = area
          End If
          ' move on, understanding that for any NEXT rectangle this R must be the upperbound.
          T = R
        End If

      Else 'R.Y < L.Y
        ' a point with y < L.Y
        ' if it is below B we can ignore it.
        ' if it is above B, it is the R-bound for the rectangle bounded by L,T,B
        If (R.Y > B.Y) Then
          ' process the rectangle
          If area > result Then
            result = area
          End If
          ' move on, understanding that for any NEXT rectangle this R must be the lowerbound.
          B = R
        End If

      End If

      indx += 1
    End While

    Return result

The overall solution is, of course: find for each point P, the optimum among opt(P,Left), opt(P,Right), opt(P,Top), opt(P,Bottom), and then find the maximum over all P. The varieties for Right, Top, Bottom are of course very similar to the opt(Left) that I sketched out above. The pre-sorting (to get indices for x-order and for y-order (for handling the (P,Top) and (P,Bottom)-cases) are O(nLogn), the local optimizations are each O(n) - view the code. So the overall complexity is O(n^2).

Note added - because the original formulation was not absolutely clear to me: IF rectangles can also be bounded by CORNER-points, then the above needs a few minor adjustments (mostly adding equal signs to inequality conditions), but it won't change the algorithm in essence.

share|improve this answer

The easiest way to do this is calculating all possible areas in a while loop and grab the maximum one at the end.

share|improve this answer
I don't think that's correct, it's a bit unclear in the question but it seems the solution rectangle cannot contain other points of the set. –  Mathias Oct 20 '12 at 6:48
What i mean is to create a loop and calculate all area of all possible rectangle's areas( with no point inside them) and just grab the biggest one. There are many other ways to do this but i thought this could be the fastest way to achieve the goal.(just ignore the slow performance of this solution). –  Michel Kogan Oct 20 '12 at 7:26

You dont really need four points.
Find the topLeft and bottomRight Point that makes a rectangular shape.
Loop through the array and just keep track/update those two point.
Once out of the loop just return (topLeft.x - bottomRight-x)*(topLeft.y - bottomRight-y);

there you go

share|improve this answer
Firstly, The OP has said the rectangle should not contain other Point (from the parameters) and also, the rectangle corners should be part of the parameters. –  st0le Oct 20 '12 at 5:02
yeah.... "track/update" if points[i].x > topLeft.x && point[i].y < topLeft.y then its the new topLeft. do the same thing-ish for bottomRight. this will ensure that the rectangular shape in topLeft and bottomRight wont have any points in them. –  antz Oct 20 '12 at 5:05
Sure, but how can your prove its the maximal area? –  st0le Oct 20 '12 at 7:02
You are right. It won't. But this can be fixed if you have another check condition while updating your topLeft/bottomRight. so if points[i].x > topLeft.x && point[i].y < topLeft.y then tempNewTopLeft = point[i]. so, if (tempNewTopLeft.x - bottomRight-x)*(tempNewTopLeft - bottomRight-y) > (topLeft.x - bottomRight-x)*(topLeft.y - bottomRight-y) then topLeft = tempNewTopLeft; –  antz Oct 20 '12 at 10:53
I would feel like its just bunch of comparision of if's. While looping through the array. if point[i] is qualified to be either topLeft or bottomRight. then make it a temp one and compare it with the current topLeft and bottomRight. and If the temp has a greater rectangular area, then it replaces topLeft/bottomRight. so, 1) if's to see if point[i] qualifies 2) if's to see whether it has greater rectangular area or not –  antz Oct 20 '12 at 10:57

i can do this in O(N^2*Log(N)).

first put all the points in a set so we can check whether a point exist in O(Log(N)).

enumerate 2 points on the diagonal, which costs O(N^2) and then the rectangle is determined, check whether the other 2 points exists then you know whether you can get it, if you do, update the answer.

share|improve this answer

Your Answer


