Checking if a list of coordinates defines a closed, exact rectangle

I have to determine if an N sized list of coordinates defines a closed, exact rectangle.

I start with the question "How do I check if a list of coordinates is in the shape of a rectangle?"

The answer is:

• First and last element in cordX and cordY have to be equal.

• Difference between another key should be equal to 1.

• Value for key has to be const.

Could you tell me if this is elegant and efficient code?

```
public class BoardPosition {
private int x;
private int y;

public int getX() {
return x;
}

void setX(int x) {
this.x = x;
}

public int getY() {
return y;
}

void setY(int y) {
this.y = y;
}

public BoardPosition(int pX, int pY) {
y = pY;
x = pX;
}
}

private boolean checkifIsRectangle(ArrayList lettersPosition) {
TreeMap cordsX = new TreeMap();
TreeMap cordsY = new TreeMap();

for (BoardPosition b : lettersPosition) {
if (!cordsX.containsKey(b.getX())) cordsX.put(b.getX(), 1);
else {
cordsX.put(b.getX(), cordsX.get(b.getX()) + 1);
}

if (!cordsY.containsKey(b.getY())) cordsY.put(b.getY(), 1);
else {
cordsY.put(b.getY(), cordsY.get(b.getY()) + 1);
}
}
boolean xIsValid = true;
boolean yIsValid = true;

//1
if (cordsX.values().toArray()[0] != cordsX.values().toArray()[cordsX.values().toArray().length - 1])
xIsValid = false;
if (cordsY.values().toArray()[0] != cordsY.values().toArray()[cordsY.values().toArray().length - 1])
yIsValid = false;

//2
int xKeyTest = -1;
for (Integer i : cordsX.keySet()) {
if (xKeyTest == -1) {
xKeyTest = i;
continue;
}
if ((i - xKeyTest) != 1

Proposed solution

Okay BoardPosition should be an immutable data structure like this:

public class BoardPosition {
        public final int x;
        public final int y;

        public BoardPosition(int pX, int pY) {
                y = pY;
                x = pX;
        }
}

You should never specify which specific implementation of List you want but rather that you want a "list" or even a "collection" of positions. See Liskov Substitution Principle.
This is better:

private boolean checkifIsRectangle(List lettersPosition) {

This can be done better:

for (BoardPosition b : lettersPosition) {
            if (!cordsX.containsKey(b.getX())) cordsX.put(b.getX(), 1);
            else {
                cordsX.put(b.getX(), cordsX.get(b.getX()) + 1);
            }

            if (!cordsY.containsKey(b.getY())) cordsY.put(b.getY(), 1);
            else {
                cordsY.put(b.getY(), cordsY.get(b.getY()) + 1);
            }
        }

By avoiding repeated look ups in the tree map, like this:

for (BoardPosition b : lettersPosition) {
            Integer x = cordsX.get(b.x);
            x = (x == null) ? 1 : x + 1;
            cordsX.put(b.x, x);

            Integer y = cordsY.get(b.y);
            y = (y == null) ? 1 : y + 1;
            cordsY.put(b.y, y);
        }

Around //1 you're creating many unnecessary copies of the values. Consider calling toArray() only once.

This:

//2
        int xKeyTest = -1;
        for (Integer i : cordsX.keySet()) {
            if (xKeyTest == -1) {
                xKeyTest = i;
                continue;
            }
            if ((i - xKeyTest) != 1) {
                xIsValid = false;
                break;
            }
            xKeyTest = i;
        }

Should be:

//2
        int xKeyTest = -1;
        for (Integer i : cordsX.keySet()) {
            if (xKeyTest != -1 && (i - xKeyTest) != 1) {
                xIsValid = false;
                break;
            }
            xKeyTest = i;
        }

And similar for Y.

And finally //3 is rather clumsy.

//3
        ArrayList xValueArray = new ArrayList(cordsX.values());
        int xTestValue = -1;
        for (int i = 1; i  yValueArray = new ArrayList(cordsY.values());
        int yTestValue = -1;
        for (int i = 1; i < yValueArray.size() - 2; i++) {
            if (yTestValue == -1) {
                yTestValue = yValueArray.get(i);
                continue;
            }
            if (yTestValue != yValueArray.get(i)) {
                yIsValid = false;
                break;
            }
        }

        return (xIsValid && yIsValid);
    }

If you want to make sure all list entries have the same value, do like this:

boolean isSame(List list){
        Integer first = list.get(0);
        for (int i = 1; i < list.size(); i++) {
            if (first != list.get(i)) {
                return false;
            }
        }
        return true;
    }

In the end your algorithm is \$\mathcal{O}(n\log n)\$ although there is a lot of iteration going on and I would say it's on the slow side of the spectrum.

A better solution

A faster way of doing this would be:

```
package test;

import java.util.Collections;
import java.util.Comparator;
import java.util.Iterator;
import java.util.List;

public class CheckRectangle{

public static class Point{
final int x;
final int y;

Point(int aX, int aY){
x = aX;
y = aY;
}
}

private static class ByX implements Comparator{
@Override
public int compare(Point o1, Point o2){
int v = Integer.compare(o1.x, o2.x);
if( v == 0 )
return Integer.compare(o1.y, o2.y);
return v;
}
}

static boolean isRectangle(List aPoints){
Collections.sort(aPoints, new ByX());

int ymax = Integer.MIN_VALUE;
int ymin = Integer.MAX_VALUE;

{
Iterator it = aPoints.iterator();
Point prev = null;
while( it.hasNext() ){
Point next = it.next();
if( prev != null && prev.x == next.x && prev.y == next.y )
it.remove();
prev = next;

ymax = Math.max(ymax, prev.y);
ymin = Math.min(ymin, prev.y);
}
}

int xmax = aPoints.get(aPoints.size() - 1).x;
int xmin = aPoints.get(0).x;

if( xmax == xmin ){ // Special case the vertical stick
return (ymax - ymin + 1) == aPoints.size();
}

if( ymax == ymin ){ // Special case the horizontal stick
return (xmax - xmin + 1) == aPoints.size();
}

// Number of (non-overlapping) grids in either direction
int w = (xmax - xmin + 1);
int h = (ymax - ymin - 1);

int numGrids = 2 h + 2 w;
if( aPoints.size() != numGrids )
return false; // Wrong number of points

// For a rectangle, there must be exactly h+2 points with x == xmin
if( aPoints.g

StackExchange Code Review Q#54488, answer score: 9