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 &lt;1:size-2> 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&lt;BoardPosition&gt; lettersPosition) {
        TreeMap&lt;Integer, Integer&gt; cordsX = new TreeMap&lt;Integer, Integer&gt;();
        TreeMap&lt;Integer, Integer&gt; cordsY = new TreeMap&lt;Integer, Integer&gt;();

        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) {
                xIsValid = false;
                break;
            }
            xKeyTest = i;
        }

        int yKeyTest = -1;
        for (Integer i : cordsY.keySet()) {
            if (yKeyTest == -1) {
                yKeyTest = i;
                continue;
            }
            if ((i - yKeyTest) != 1) {
                yIsValid = false;
                break;
            }
            yKeyTest = i;
        }

        //3
        ArrayList&lt;Integer&gt; xValueArray = new ArrayList&lt;Integer&gt;(cordsX.values());
        int xTestValue = -1;
        for (int i = 1; i &lt; xValueArray.size() - 2; i++) {
            if (xTestValue == -1) {
                xTestValue = xValueArray.get(i);
                continue;
            }
            if (xTestValue != xValueArray.get(i)) {
                xIsValid = false;
                break;
            }
        }

        ArrayList&lt;Integer&gt; yValueArray = new ArrayList&lt;Integer&gt;(cordsY.values());
        int yTestValue = -1;
        for (int i = 1; i &lt; yValueArray.size() - 2; i++) {
            if (yTestValue == -1) {
                yTestValue = yValueArray.get(i);
                continue;
            }
            if (yTestValue != yValueArray.get(i)) {
                yIsValid = false;
                break;
            }
        }


        return (xIsValid &amp;&amp; yIsValid);
    }
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&lt;BoardPosition&gt; 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 &amp;&amp; (i - xKeyTest) != 1) {
                xIsValid = false;
                break;
            }
            xKeyTest = i;
        }


And similar for Y.    

And finally //3 is rather clumsy.

        //3
        ArrayList&lt;Integer&gt; xValueArray = new ArrayList&lt;Integer&gt;(cordsX.values());
        int xTestValue = -1;
        for (int i = 1; i &lt; xValueArray.size() - 2; i++) {
            if (xTestValue == -1) {
                xTestValue = xValueArray.get(i);
                continue;
            }
            if (xTestValue != xValueArray.get(i)) {
                xIsValid = false;
                break;
            }
        }

        ArrayList&lt;Integer&gt; yValueArray = new ArrayList&lt;Integer&gt;(cordsY.values());
        int yTestValue = -1;
        for (int i = 1; i &lt; yValueArray.size() - 2; i++) {
            if (yTestValue == -1) {
                yTestValue = yValueArray.get(i);
                continue;
            }
            if (yTestValue != yValueArray.get(i)) {
                yIsValid = false;
                break;
            }
        }


        return (xIsValid &amp;&amp; yIsValid);
    }


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

    boolean isSame(List&lt;Integer&gt; list){
        Integer first = list.get(0);
        for (int i = 1; i &lt; 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&lt;Point&gt;{
      @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&lt;Point&gt; aPoints){
      Collections.sort(aPoints, new ByX());

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

      {
         Iterator&lt;Point&gt; it = aPoints.iterator();
         Point prev = null;
         while( it.hasNext() ){
            Point next = it.next();
            if( prev != null &amp;&amp; prev.x == next.x &amp;&amp; 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.get(h + 1).x != xmin )
         return false;

      // And exactly h+2 points with x == xmax
      if( aPoints.get(numGrids - (h + 2)).x != xmax )
         return false;

      return true;
   }
}


This performs in \$\mathcal{O}(n\log n)\$ as well, but it has much less iteration and memory accesses.

The key here is to sort by 'x' coordinate (you can do it by 'y' too). Due to the sort the list structure is very specific for rectangles and you just need to check a few specific values in the list to be sure that you have a rectangle.

If you don't believe the correctness of my solution, you can execute the unit tests available here: https://gist.github.com/EmilyBjoerk/4f015a7e1b394a73e4cc .