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

  • 1

    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
    

Log in to reply
 

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