Simple Java Solution - Square distances


  • 10

    Just find the square of lenghts, and validate that

    1. There are only two equal longest lenghts.
    2. The non longest lengths are all equal.
    public boolean validSquare(int[] p1, int[] p2, int[] p3, int[] p4) {
        long[] lengths = {length(p1, p2), length(p2, p3), length(p3, p4),
                length(p4, p1), length(p1, p3),length(p2, p4)}; // all 6 sides
    
        long max = 0, nonMax = 0;
        for(long len : lengths) {
            max = Math.max(max, len);
        }
        int count = 0;
        for(int i = 0; i < lengths.length; i++) {
            if(lengths[i] == max) count++;
            else nonMax = lengths[i]; // non diagonal side.
        }
        if(count != 2) return false; // diagonals lenghts have to be same.
    
        for(long len : lengths) {
            if(len != max && len != nonMax) return false; // sides have to be same length
        }
        return true;
    }
    private long length(int[] p1, int[] p2) {
        return (long)Math.pow(p1[0]-p2[0],2) + (long)Math.pow(p1[1]-p2[1], 2);
    }

  • 0

    NiuBility :P


  • 0
    G

    My solution same thought, C++

    class Solution {
    public:
        bool validSquare(vector<int>& p1, vector<int>& p2, vector<int>& p3, vector<int>& p4) {
            vector<float> edges;
            edges.push_back(norm(p1, p2));
            edges.push_back(norm(p2, p3));
            edges.push_back(norm(p3, p4));
            edges.push_back(norm(p4, p1));
            edges.push_back(norm(p2, p4));
            edges.push_back(norm(p1, p3));
            std::sort(edges.begin(), edges.end());
            return edges[0] == edges[1] && edges[1] == edges[2] && edges[2] == edges[3] && edges[3] != edges[4] && edges[4] == edges[5];
        }
        float norm(vector<int>& p1, vector<int>& p2){
            return std::sqrt((p1[0]-p2[0])*(p1[0]-p2[0]) + (p1[1]-p2[1])*(p1[1]-p2[1]));
        }
    };
    

  • 2

    if four points construct a square, the lines connecting a, b, c, d must be 4 and 2. 4 is the boarder and 2 is the diagonal。
    a--------------b
    |
    |
    |
    c--------------d

    public boolean validSquare(int[] p1, int[] p2, int[] p3, int[] p4) {
       
      List<Integer> distances = new ArrayList();
      distances.add(getDistance(p1, p2));
      distances.add(getDistance(p1, p3));
      distances.add(getDistance(p1, p4));
      distances.add(getDistance(p2, p3));
      distances.add(getDistance(p2, p4));
      distances.add(getDistance(p3, p4));
      
      List<Integer> group1 = new ArrayList();
      List<Integer> group2 = new ArrayList();
      for(int distance: distances){
        if(group1.size() == 0) group1.add(distance);
        else {
          if(distance == group1.get(0)) group1.add(distance);
          else {
            if(group2.size() == 0) group2.add(distance);
            else {
              if(group2.get(0) == distance) group2.add(distance);
            }
          }
        }
      }
    
      if((group1.size() == 2 && group2.size() == 4) || (group1.size() == 4 && group2.size() == 2)) return true;
      else return false;   
    }
    
    int getDistance(int[] a, int[] b){
      int x = a[0] - b[0];
      int y = a[1] - b[1];
      return x * x + y * y;
    }

  • 0

    Is this a counter example ?
    a (0, 0), b (1, 0), c (1/2, sqrt(3)/2), d(1/2, 1+sqrt(3)/2)

    abc forms a isosceles triangle and d is right above c with cd == edge of the isosceles triangle


  • 0

    @dreamchase said in Simple Java Solution - Square distances:

    0, 0), b (1, 0), c (1/2, sqrt(3)/2), d(1/2, 1+sqrt(3)/2)

    The code doesn't work on decimal values, so I changed my code and tested, and you might be right.

    I think you meant abc forms equilateral triangle with sides = 1. And you draw a line of length = 1 from top edge upwards. Good catch!

            System.out.println(s.validSquare(new double[] {0,0},
                    new double[] {1,0},
                    new double[] {0.5, Math.sqrt(3)/2},
                    new double[] {0.5, 1 + Math.sqrt(3)/2}));
    

    These will be corresponding lengths.

    1.0
    0.9999999999999999
    1.0
    3.732050807568877
    0.9999999999999999
    3.732050807568877
    

  • 0
    class Solution {
        public boolean validSquare(int[] p1, int[] p2, int[] p3, int[] p4) {
            int[] dis = new int[]{distance(p1, p2), distance(p1, p3), distance(p1, p4), distance(p2, p3)
                                    , distance(p2, p4), distance(p3, p4)};
            Map<Integer, Integer> map = new HashMap<>();
            int max = 0;
            for (int i : dis) {
                max = Math.max(max, i);
                if (!map.containsKey(i)) {
                    map.put(i, 1);
                } else {
                    map.put(i, map.get(i) + 1);
                }
            }
            return map.get(max) == 2 && map.size() == 2;
        }
        
        public int distance(int[] p1, int[] p2) {
            return (p2[0] - p1[0]) * (p2[0] - p1[0]) + (p2[1] - p1[1]) * (p2[1] - p1[1]);
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.