patternjavaMinor

Get Rectangle Count from Given List of Co-ordinates

Submitted by: @import:stackexchange-codereview·Mar 10, 2026·

Viewed 0 times

rectangleordinateslistgetcountfromgiven

Problem

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 < 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); // poi

Solution

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()




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; 
    }
    //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 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 points = new TreeSet(/* 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 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
            }
        }
    }
}

Code Snippets

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

@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;
}

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);
}

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
            }
        }
    }
}

Context

StackExchange Code Review Q#31819, answer score: 2

Revisions (0)

No revisions yet.