593. Valid Square.md

593. Valid Square

---

leetcode Daily Challenge on November 11th, 2020.

leetcode.cn Daily Challenge on July 29th, 2022.

---

Difficulty : Medium

Related Topics : Math

---

Given the coordinates of four points in 2D space p1, p2, p3 and p4, return true if the four points construct a square.

The coordinate of a point pi is represented as [xi, yi]. The input is not given in any order.

A valid square has four equal sides with positive length and four equal angles (90-degree angles).

Example 1:

Input: p1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,1]
Output: true

Example 2:

Input: p1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,12]
Output: false

Example 3:

Input: p1 = [1,0], p2 = [-1,0], p3 = [0,1], p4 = [0,-1]
Output: true

Constraints:

p1.length == p2.length == p3.length == p4.length == 2 -10^4 <= xi, yi <= 10^4

---

Solution

• mine
  • Java

    • Runtime: 3 ms, faster than 6.94%, Memory Usage: 38.3 MB, less than 5.16% of Java online submissions

      public boolean validSquare(int[] p1, int[] p2, int[] p3, int[] p4) {
          int[][] arr = {p1, p2, p3, p4};
          Map<Integer, Set<Double>> map = new HashMap<>();
          if (!getAndCheckDis(arr, map)) return false;
      
          for (int i = 0; i < arr.length; i++) {
              List<Double> list = new ArrayList<>(map.get(i));
              double max = Math.max(list.get(0), list.get(1));
              double min = Math.min(list.get(0), list.get(1));
              if (Math.abs(max / min - Math.sqrt(2)) > 0.0000001) {
                  return false;
              }
          }
          return true;
      }
      
      boolean getAndCheckDis(int[][] arr, Map<Integer, Set<Double>> map) {
          int n = arr.length;
          for (int i = 0; i < n; i++) {
              Set<Double> seti = map.getOrDefault(i, new HashSet<>());
              for (int j = i + 1; j < n; j++) {
                  int x = arr[i][0] - arr[j][0];
                  int y = arr[i][1] - arr[j][1];
                  double dis = Math.sqrt(x * x + y * y);
                  Set<Double> setj = map.getOrDefault(j, new HashSet<>());
                  seti.add(dis);
                  setj.add(dis);
                  map.put(j, setj);
              }
              map.put(i, seti);
              if (seti.size() != 2) return false;
          }
          return true;
      }
      

    • Runtime: 5 ms, faster than 9.16%, Memory Usage: 42.5 MB, less than 27.90% of Java online submissions

      public static boolean validSquare(int[] p1, int[] p2, int[] p3, int[] p4) {
          int[][] arr = {p1, p2, p3, p4};
          HashMap<Integer, Integer> map = new HashMap<>();
          List<Integer> list = new ArrayList<>();
          for (int i = 0; i < arr.length; i++) {
              for (int j = 0; j < arr.length; j++) {
                  if (i == j) {
                      continue;
                  }
                  int x = arr[i][0] - arr[j][0];
                  int y = arr[i][1] - arr[j][1];
                  int dis = x * x + y * y;
                  map.put(dis, map.getOrDefault(dis, 0) + 1);
              }
              if (map.size() != 2) {
                  return false;
              }
              list.addAll(map.keySet());
              int a = list.get(0);
              int b = list.get(1);
              if (a > b == map.get(a) > map.get(b)) {
                  return false;
              }
          }
          return true;
      }
      

---

• the most votes

• Runtime: 0 ms, faster than 100.00%, Memory Usage: 36.8 MB, less than 77.07% of Java online submissions

  public boolean validSquare(int[] p1, int[] p2, int[] p3, int[] p4) {
      int d1 = getDist(p1, p2);
      if (d1 == 0 || d1 != getDist(p3, p4)) {
          return false;
      }
      int d2 = getDist(p1, p3);
      if (d2 == 0 || d2 != getDist(p2, p4)) {
          return false;
      }
      int d3 = getDist(p1, p4);
      if (d3 == 0 || d3 != getDist(p2, p3)) {
          return false;
      }
      return d1 == d2 || d2 == d3 || d1 == d3;
  }
  
  public int getDist(int[] p1, int[] p2) {
      return (p1[0] - p2[0]) * (p1[0] - p2[0]) + (p1[1] - p2[1]) * (p1[1] - p2[1]);
  }
  

---