Get Rectangle Count from Given List of Co-ordinates 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


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. 
for inside for inside if inside.... you get the picture... Is it nasty?
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 &lt; MIN_POINTS_TO_CREATE_RECTANGLE)
        return 0;

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

    for(int i = 0; i &lt; 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 &lt; points.length; i++) {
        Point leftDown = points[i];

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

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

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

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

                        rectangleCount++;

                    }

                }

            }

        }

    }
    return rectangleCount;
}


I also have a custom Point class that implements Comparable&lt;Point&gt;. 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 ;)
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() &lt; 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() &lt; p.getX()) { 
        return -1;
    } 
    if (this.getX() &gt; 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 &lt;T&gt; 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&lt;Point&gt; points = new TreeSet&lt;Point&gt;(/* comparator goes here */);

for(int i = 0; i &lt; 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&lt;Point&gt; 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 &gt; 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
            }
        }
    }
}