Get Rectangle Count from Given List of Co-ordinates

Question

Problem Description

Write a program to find the maximum number of rectangles that can be formed both horizontal and vertical with the help of a given n number of coordinate(x,y) points. [x,y points will always be positive].

The method getRectangleCount takes 1 input parameter which is an int array called coOrdinates.

The method getRectangleCount takes the coordinates as a 2D integer array and returns the maximum number of rectangles as an integer.

public int getRectangleCount(int[][] coOrdinates)

There is no need to count the rectangles that can be created from the overlapping rectangles.

Example

Input : int coordinates[][] = { {1,1}, {7,1}, {1,4}, {1,5}, {7,4}, {7,5} }

Output : Returns 3

Explanation:

Three rectangles can be formed.

First -

    (1,4)----(7,4)
     |         |
     |         |    
    (1,1)----(7,1) 

Second -

    (1,5)----(7,5)
     |         |
     |         |    
    (1,1)----(7,1) 

Third -

    (1,5)----(7,5)
     |         |
     |         |    
    (1,4)----(7,4)

---

My Concerns

1. Is it readable? Is it maintainable? I intentionally didn't comment in the code because I want to see if the code is self-explanatory or not.
2. for inside for inside if inside.... you get the picture... Is it nasty?
3. Can it be optimized, as it is from a programming challenge, time is a factor.

My Solution

You can browse the GitHub Project for more info.

public int getRectangleCount(int [][]coOrdinates) {

    // exception handling part coded here... forget about it

    final int MIN_POINTS_TO_CREATE_RECTANGLE = 4;

    // can't make a rectangle with less than 4 points
    if(coOrdinates.length < MIN_POINTS_TO_CREATE_RECTANGLE)
        return 0;

    final Point []points = new Point[coOrdinates.length];

    for(int i = 0; i < coOrdinates.length; i++)
        points[i] = new Point(coOrdinates[i][0], coOrdinates[i][1]);

    Arrays.sort(points); // points are sorted like (1,1) (1,3) (3,1) (3,3)....

    int rectangleCount = 0;
    for(int i = 0; i < points.length; i++) {
        Point leftDown = points[i];

        for(int j = i+1; j < points.length; j++) {
            Point leftUp = points[j];

            if(leftDown.getX() == leftUp.getX()) {

                for(int k = j+1; k < points.length; k++) {
                    Point rightDown = points[k];
                    Point probableRightUp = new Point(rightDown.getX(), leftUp.getY());

                    if((leftDown.getY() == rightDown.getY())
                                &&
                        probableRightUp.existsIn(points)) {

                        rectangleCount++;

                    }

                }

            }

        }

    }
    return rectangleCount;
}

I also have a custom Point class that implements Comparable<Point>. Point overrides compareTo() method like following

@Override
public int compareTo(Point p) {
    if(Integer.compare(this.getX(),p.getX()) == 0)
    {
        return Integer.compare(this.getY(), p.getY());
    }
    return Integer.compare(this.getX(),p.getX());
}

and method existsIn(Point []graph) works like as you think. It returns true if this exists in the graph else false.

Yes I will create a Points collection class later and will move existsIn(Point []graph). I will also change the signature to

public static boolean existsIn(Point []graph, Point toCheck) // Promise I will ;)

Answer 1

On the whole it's not at all bad, I find it readable and I'm sure that it does the job (one caveat to this is how does it handle cases where you have multiple instances of the same point e.g. {{1,1},{1,1},{1,2},{2,1}}), a few things that you could do to improve it..

• For uniqueness and sorting consider using a TreeSet, this will have an impact on the rest of your algorithm though as you can no longer rely on iterating using an index (see below).
• As @DaveJarvis says, it is preferable to have the square brackets immediately following the type - as they form a part of the type (2D array of ints vs int).
• final int MIN_POINTS_TO_CREATE_RECTANGLE = 4; If this is the only piece of code to care that a rectangle has four corners it is fine to define it in method scope. If other methods might care, or if there is any chance it might need to be publicly visible then move it up to class level.
• My personal preference is to always use braces even for one line conditionals. It makes your code slightly longer, but I find it more readable and it reduces the chances of bugs down the line (when someone wants to make it a two+ line conditional). This may relate to the question around Point uniqueness as you may consider adding a test for uniqueness (or using a Set) which would then make your conditional code longer.
• Small things like breaking both the creation and sorting of the Point[] into new methods. It is almost trivial in this case but it will make your code easier to read, more testable and it lends itself to extensibility down the line (if for example you wanted to have different creation strategy down the line).
• leftDown, leftUp and rightDown do not add anything to your algorithm, instead consider naming i,j, and k more sensibly.
• If leftDown.getX() < leftUp.getX() you know you have reached a point where no other matches can ever be found. To fix this you can use a while loop instead

e.g

int j = i + 1;
//don't forget to handle index out of bounds
while (points[i].getX() == points[j++].getX()) { }

• Similarly you can be sure that if k == points.length - 1 then you are not going to find a match.
• Your k iteration is pointless if leftDown.getY() != rightDown.getY() so that test should move up and delay your creation of probableRightUp.
• Your compareTo method can be made a little neater, either write the result of the initial compare to a variable and return it immediately if non-zero, or consider doing the comparison yourself

e.g

@Override
public int compareTo(Point p) {
    if (this.getX() < p.getX()) { 
        return -1;
    } 
    if (this.getX() > p.getX()) { 
        return 1; 
    }
    //and for Y
    ...
    return 0;
}

-. When you are coding your existsIn method start thinking in templates. Sure it's not necessary now, but it costs nothing to write public static <T> boolean existsIn(T[] array, T element) and you've got a utility function you can use forever.

One thing that would concern me about this method is the Cyclomatic Complexity due to the number of loops and conditionals. Consider how you could break things down, e.g The content of your k loop can be broken out into code which finds/verifies the rectangle is complete. As a rule each method should have a role as discrete as possible, again this makes things more testable and more readable (when coupled with sensible naming).

---

So using a TreeSet. Your initial code becomes:

final SortedSet<Point> points = new TreeSet<Point>(/* comparator goes here */);

for(int i = 0; i < coOrdinates.length; i++) {
    Point p = new Point(coOrdinates[i][0], coOrdinates[i][1]);
    points.add(p);
}

Your iterations would need to evolve to use the SortedSet#tailSet or SortedSet#subSet methods. Both of these are just new views on the same data so they are cheap operations.

A pseudo approach:

for (Point leftDown : points) {
    //You would pull this into a new method
    SortedSet<Point> potentialLeftUp =  points.subSet(leftDown, new Point(leftDown.getX(), somePrecalculatedMaxY);

    for (Point leftUp : potentialLeftUp) {
        //no testing needed as you know it shares X

        //now build subset (potentialRightDown) where X > leftDown.getX and Y == leftDown.getY (this will be more manual as you are X sorted)

        for (Point rightDown : potentialRightDown) {
            //build probableRightUp
            if (points.contains(probableRightUp) {
                 //increment count
            }
        }
    }
}

Answer 2

Assuming you count rectangle by exhaustion (case by cases), you'll never be able to have a complexity smaller than the number of rectangles.

My feeling is that the highest number of "rectangles per point" is obtained when working on a grid of width n (n*n points).

Indeed, in that case, we have :

• 1 = 1*1 rectangle of size n
• 4 = 2*2 rectangles of size n-1
• 9 = 3*3 rectangles of size n-2
• ...
• (n-1)*(n-1) rectangles of size 1

for a total of (n-1)n(2*n-1)/6. This tells us that the current strategy won't be able to be better than O(n^3).

Now, what you could do to is maintain 2 arrays instead of one :

• A1 sorted by (x,y) - this is O(n*log(n))
• A2 sorted by (y,x) - this is O(n*log(n))

Then do something like :

 - foreach p1 in A1:
    | find first p2 such that p1.x = p2.x (and p1.y < p2.y) using binary search in A1
    | find last  p3 such that p1.x = p3.x using binary search in A1
    | find first p4 such that p1.y = p4.y (and p1.x < p4.x) using binary search in A2
    | find last  p5 such that p1.y = p4.y using binary search in A2
    | if (p2 exists and p4 exists):
        | foreach p6 in (p2..p3):
           | foreach p7 in (p4..p5):
              | if (find p8 such that p8.y = p6.y and p8.x = p7.x using binary search in A1 or A2):
                  | rectangle++

This solution is symetric in terms of x and y.

Its complexity seems to be ~ n^3*log(n) in the worst case (points are a grid) which is not too far from the optimal.

The complexity is ~ n*log(n) in cases where no more than 2 points are on the same horizontal or vertical line.

Tiny optimisations would be starting the binary search in the smallest possible range :

• looking for p2 from p1 onward
• looking for p3 from p2 onward
• looking for p5 from p4
• looking for p8 from p3 or p5.

Now, assuming you want to keep the solution with a single sorted array :

• you could break if "if(leftDown.getX() == leftUp.getX()) {" wasn't verified as it seems that we went too far.
• existsIn could be given an additional parameter to limit the space we are using for the lookup.
• I think the interface would be clearer if the function was to take an array of point (and maybe having a different function converting from coordinates to points).
• I am not sure there is any point in having a special case for array with a length smaller than 4 as they would be handled properly and very quickly anyway.