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

Question

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:

1. First and last element in cordX and cordY have to be equal.
2. Difference between another key should be equal to 1.
3. Value for key <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<BoardPosition> lettersPosition) {
        TreeMap<Integer, Integer> cordsX = new TreeMap<Integer, Integer>();
        TreeMap<Integer, Integer> cordsY = new TreeMap<Integer, Integer>();

        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<Integer> xValueArray = new ArrayList<Integer>(cordsX.values());
        int xTestValue = -1;
        for (int i = 1; i < xValueArray.size() - 2; i++) {
            if (xTestValue == -1) {
                xTestValue = xValueArray.get(i);
                continue;
            }
            if (xTestValue != xValueArray.get(i)) {
                xIsValid = false;
                break;
            }
        }

        ArrayList<Integer> yValueArray = new ArrayList<Integer>(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);
    }

Answer 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<BoardPosition> 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<Integer> xValueArray = new ArrayList<Integer>(cordsX.values());
        int xTestValue = -1;
        for (int i = 1; i < xValueArray.size() - 2; i++) {
            if (xTestValue == -1) {
                xTestValue = xValueArray.get(i);
                continue;
            }
            if (xTestValue != xValueArray.get(i)) {
                xIsValid = false;
                break;
            }
        }

        ArrayList<Integer> yValueArray = new ArrayList<Integer>(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<Integer> 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<Point>{
      @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<Point> aPoints){
      Collections.sort(aPoints, new ByX());

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

      {
         Iterator<Point> 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.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 .

Answer 2

Constructors are usually placed at the top of the class, just below the instance variables.

---

If Statements:

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

Don't put the true block on the same line as the if clause. It makes the code harder to read as many people assumed that only the if clause is on the first line. This is especially true when you have an else clause.

You should pick a single style of writing your if-else statements. You have a mix of in-lining the true clause, using braces for a single line clause and omitting the braces for a single line clause. Being consistent will make the code more readable. My preference is to always use braces. This will prevent errors when a second statement is added, but since braces were not used, the statement is always executed.

---

Use Helper Functions:

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;

These if clauses are long and hard to read. Addittionally, they are repeating the same code, but use a different Map. Instead the code could be written like this:

boolean isFirstSameAsLast(TreeMap<Integer, Integer> map) {
    Integer[] values = map.values.toArray();
    return values[0] == values[values.length -1];
}

//...

boolean xIsValid = !isFirstSameAaLast(cordsX);
boolean yIsValid = !isFirstSameAaLast(cordsX);

This is much more readable. The function name tells you what is being checked. Storing the value array into a variable first makes the comparison much cleaner.

Note: This function assumes that the map has at least one value. This will NOT be true if the List passed to the function is empty.

Steps 2 and 3 Can also be broken down into sub-functions that are applied to a single List argument.

---

Optimization:

Once you have a false value in xIsValid or yIsValid, you know that the result is false. You can either return immediately or use the following technique:

boolean isValid = check1();
isValid = isValid && check2();
isValid = isValid && check3();
return isValid;

The && (boolean and) operator will short-circuit and not execute the additional checks if the value is already false. You can also put all of the checks in a single chained statement if you don't need to do any setup work between each check.

Answer 3

I realized that in addition to my previous answer it is possible to do this in an even faster \$\mathcal{O}(n)\$ time complexity. Instead of making my previous answer even longer than it already is, I'll provide the code here as a reference with a caveat: It will not return a correct result for the special cases where all points form a vertical or horizontal line with thickness 1. It's a matter of definition if one wants these to count as rectangles or not.

The handling of those two special cases (xmin==xmax and ymin==ymax) is left to the reader.

Here is the implementation:

public class CheckRectangle{

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

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

      @Override
      public String toString(){
         return "(" + x + ", " + y + ")";
      }
   }

   private static class RectangularIndexer{
      private final int lowerLineOffs;
      private final int upperLineOffs;
      private final int leftLineOffs;
      private final int rightLineOffs;

      private final int xmin;
      private final int xmax;
      private final int ymin;
      private final int ymax;

      public RectangularIndexer(int axmin, int axmax, int aymin, int aymax){
         xmin = axmin;
         xmax = axmax;
         ymin = aymin;
         ymax = aymax;
         lowerLineOffs = 0;
         upperLineOffs = lowerLineOffs + (xmax - xmin + 1);
         leftLineOffs = upperLineOffs + (xmax - xmin + 1);
         rightLineOffs = leftLineOffs + (ymax - ymin - 1);
      }

     public int index(Point aP){
         if( aP.y == ymin ){
            return aP.x - xmin;
         }
         else if( aP.y == ymax ){
            return upperLineOffs + aP.x - xmin;
         }
         else{
            if( aP.x == xmin ){
               return leftLineOffs + aP.y - ymin - 1;
            }
            else if( aP.x == xmax ){
               return rightLineOffs + aP.y - ymin - 1;
            }
            else{
               return -1;
            }
         }
      }
   }

   static boolean isRectangle(List<Point> aPoints){
      if( aPoints.size() == 1 )
         return true;

      // Phase 1
      int xmax = Integer.MIN_VALUE;
      int xmin = Integer.MAX_VALUE;
      int ymax = Integer.MIN_VALUE;
      int ymin = Integer.MAX_VALUE;

      for(Point p : aPoints){
         xmax = Math.max(xmax, p.x);
         xmin = Math.min(xmin, p.x);
         ymax = Math.max(ymax, p.y);
         ymin = Math.min(ymin, p.y);
      }

      // Phase 2    
      RectangularIndexer indexer = new RectangularIndexer(xmin, xmax, ymin, ymax);
      boolean[] score = new boolean[2 * (xmax - xmin + ymax - ymin)];

      for(Point p : aPoints){
         int idx = indexer.index(p);
         if( idx < 0 )
            return false;
         score[idx] = true;
      }

      // Phase 3
      for(boolean s : score){
         if( s == false )
            return false;
      }
      return true;
   }
}

In phase 1 I determine the max and min of both dimensions. And assume a hypothetical rectangle that goes between min and max of the points.

Next in phase 2 I devise a indexing scheme that maps every point on the assumed rectangle to a unique index and any point not on the rectangle to -1. I also allocate a score vector that is as long as the indexes will go.

Then I iterate over all the points again and if any point has a negative index, it is not on the rectangle so I terminate with false. Otherwise I take the index and mark it on the score chart so that I know I have visited that point (necessary to make sure the rectangle is closed).

Finally in phase 3, I iterate over the score card to make sure every point on the rectangle was covered by at least one point. This neatly covers double points as well.

The running time is more accurately \$\mathcal{O}(2n + w+h)\$ where \$w\cdot h=n\$.

Answer 4

Regarding elegance, if your BoardPosition class is a plain data structure, make it so.

struct BoardPosition {
    int x;
    int y;
};

Second, regarding efficiency, your checkIfIsRectangle function returns (xIsValid && yIsValid), which have both been calculated at the point of return. This does not take advantage of the short-circuit guarantee of the && operator. Better directly return:

private boolean checkifIsRectangle(ArrayList<BoardPosition> lettersPosition) {
    return (xIsValid(lettersPosition) && yIsValid(lettersPosition));
}

And implement xIsValid and yIsValid in terms of functions. If xIsValid returns false, yIsValid will not even be executed.

Answer 5

Since we're all sharing methods, here's mine. Not as elegant as some, but may be considered simpler.

1. Deduplicate points.
2. Form the bounding rectangle of the points.
3. If it's a solid rectangle, then you should have width*height points.

4. If it's a hollow rectangle, then the outer ring will have 2*(width + height - 2) points and the inside 0.

   public static class BoardPosition implements Comparable<BoardPosition> {
   
       public final int x;
       public final int y;
   
       public BoardPosition(int pX, int pY) {
   
           y = pY;
           x = pX;
       }
   
       @Override
       public int compareTo(BoardPosition other) {
   
           int ydiff = other.y - y;
           if (ydiff != 0) {
   
               return ydiff;
           }
           return (other.x - x);
       }
   }
   
   private static class Partition {
   
       public final List<BoardPosition> outer;
       public final List<BoardPosition> inner;
   
       Partition(List<BoardPosition> outer, List<BoardPosition> inner) {
   
           this.outer = outer;
           this.inner = inner;
       }
   }
   
   private static class CoordSet {
   
       private final int minX;
       private final int maxX;
       private final int minY;
       private final int maxY;
   
       private final TreeSet<BoardPosition> coords;
   
       CoordSet(List<BoardPosition> lettersPosition) {
   
           coords = new TreeSet<BoardPosition>(lettersPosition);
   
           int eminX = Integer.MAX_VALUE;
           int emaxX = Integer.MIN_VALUE;
           int eminY = Integer.MAX_VALUE;
           int emaxY = Integer.MIN_VALUE;
           for (BoardPosition b : coords) {
   
               eminX = Math.min(eminX, b.x);
               emaxX = Math.max(emaxX, b.x);
               eminY = Math.min(eminY, b.y);
               emaxY = Math.max(emaxY, b.y);
           }
           minX = eminX;
           maxX = emaxX;
           minY = eminY;
           maxY = emaxY;
       }
   
       int size() {
   
           return coords.size();
       }
   
       int width() {
   
           return maxX - minX + 1;
       }
   
       int height() {
   
           return maxY - minY + 1;
       }
   
       Partition peelOffOuterRing() {
   
           List<BoardPosition> inner = new ArrayList<BoardPosition>();
           List<BoardPosition> outer = new ArrayList<BoardPosition>();
   
           for (BoardPosition pos: coords) {
   
               if ((pos.x > minX) && (pos.x < maxX) && (pos.y > minY) && (pos.y < maxY)) {
   
                   inner.add(pos);
               }
               else
               {
                   outer.add(pos);
               }
           }
           return new Partition(outer, inner);
       }
   }
   
   public static boolean isRectangle(List<BoardPosition> lettersPosition) {
   
       CoordSet coords = new CoordSet(lettersPosition);
   
       int width = coords.width();
       int height = coords.height();
   
       if (coords.size() == width*height) {
   
           return true;
       }
   
       Partition peel = coords.peelOffOuterRing();
       return ((peel.outer.size() == 2*(width + height - 2)) && (peel.inner.size() == 0));
   }