Welcome to Subscribe On Youtube

• Java
• C++
• Python
• Go

• import java.util.ArrayList;
  import java.util.Arrays;
  
  /*
  Given the coordinates of four points in 2D space, return whether the four points could construct a square.
  
  The coordinate (x,y) of a point is represented by an integer array with two integers.
  
  Example:
  Input: p1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,1]
  Output: True
  Note:
  
  All the input integers are in the range [-10000, 10000].
  A valid square has four equal sides with positive length and four equal angles (90-degree angles).
  Input points have no order.
  
   */
  
  public class Valid_Square {
  
  	// Just find the square of lengths, and validate that
  	// 1. There are only two equal longest lengths.
  	// 2. The non longest lengths are all equal. (or, a^2 + b^2 = c^2)
  
  	public boolean validSquare(int[] p1, int[] p2, int[] p3, int[] p4) {
  
  		// long in case of int overflow
  		long[] lengths = new long[]{
  							getDistLong(p1, p2),
  							getDistLong(p2, p3),
  							getDistLong(p3, p4),
  							getDistLong(p4, p1),
  							getDistLong(p1, p3),
  							getDistLong(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 getDistLong(int[] p1, int[] p2) {
  		return (long) Math.pow(p1[0] - p2[0], 2) + (long) Math.pow(p1[1] - p2[1], 2);
  	}
  
  
  	// more math other than algorithmn
  	// 2 pairs of parellel lines, and check 1 angle is 90^ (then rest 3 also 90^), special: vertical line case
  	// or, 4 lines are same length, and and check 1 angle is 90^ (then rest 3 also 90^)
  	// or, 4 lines are same length, and a^2 + b^2 = c^2
  
  
  	// getting too many redundancy of computation of diagonal and edge
  	public class Solution_shitty {
  	    public boolean validSquare(int[] p1, int[] p2, int[] p3, int[] p4) {
  
  	        if(p1 == null || p2 == null || p3 == null || p4 == null) {
  	            return false;
  	        }
  
  	        // generate baseline from p1, can make 3 lines
  	        int d1 = getDist(p1, p2);
  	        int d2 = getDist(p1, p3);
  	        int d3 = getDist(p1, p4);
  
  	        int diagonal = Math.max(Math.max(d1, d2), d3);
  	        int edge = Math.min(Math.min(d1, d2), d3);
  
  	        // iterate through rest 3 points
  	        // @note: type initialization
  	        ArrayList<int[]> all3 = new ArrayList<>(Arrays.asList(p2, p3, p4));
  	        for(int[] each: all3) {
  	            // edges are the same
  	            // diagonal is the same
  	        }
  
  	        return true;
  	    }
  
  	    // assume valid input of point
  	    private int getDist(int[] p1, int[] p2) {
  	        return (int) (Math.pow(p1[0] - p2[0], 2) + Math.pow(p1[1] - p2[1], 2));
  	    }
  	}
  }
  
  ############
  
  class Solution {
      public boolean validSquare(int[] p1, int[] p2, int[] p3, int[] p4) {
          return check(p1, p2, p3) && check(p1, p3, p4) && check(p1, p2, p4) && check(p2, p3, p4);
      }
  
      private boolean check(int[] a, int[] b, int[] c) {
          int x1 = a[0], y1 = a[1];
          int x2 = b[0], y2 = b[1];
          int x3 = c[0], y3 = c[1];
          int d1 = (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
          int d2 = (x1 - x3) * (x1 - x3) + (y1 - y3) * (y1 - y3);
          int d3 = (x2 - x3) * (x2 - x3) + (y2 - y3) * (y2 - y3);
          if (d1 == d2 && d1 + d2 == d3 && d1 > 0) {
              return true;
          }
          if (d1 == d3 && d1 + d3 == d2 && d1 > 0) {
              return true;
          }
          if (d2 == d3 && d2 + d3 == d1 && d2 > 0) {
              return true;
          }
          return false;
      }
  }
  

• // OJ: https://leetcode.com/problems/valid-square/
  // Time: O(1)
  // Space: O(1)
  class Solution {
  private:
      long long dist(vector<int>& a, vector<int>& b) {
          return pow(a[0] - b[0], 2) + pow(a[1] - b[1], 2);
      }
  public:
      bool validSquare(vector<int>& p1, vector<int>& p2, vector<int>& p3, vector<int>& p4) {
          map<long long, int> m;
          vector<vector<int>> v = {p1, p2, p3, p4};
          for (int i = 0; i < 3; ++i) {
              for (int j = i + 1; j < 4; ++j) {
                  auto d = dist(v[i], v[j]);
                  if (!d) return false;
                  m[d]++;
              }
          }
          auto a = *m.begin(), b = *m.rbegin();
          return m.size() == 2 && a.second == 4 && 2 * a.first == b.first;
      }
  };
  

• class Solution:
      def validSquare(
          self, p1: List[int], p2: List[int], p3: List[int], p4: List[int]
      ) -> bool:
          def check(a, b, c):
              (x1, y1), (x2, y2), (x3, y3) = a, b, c
              d1 = (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)
              d2 = (x1 - x3) * (x1 - x3) + (y1 - y3) * (y1 - y3)
              d3 = (x2 - x3) * (x2 - x3) + (y2 - y3) * (y2 - y3)
              return any(
                  [
                      d1 == d2 and d1 + d2 == d3 and d1,
                      d2 == d3 and d2 + d3 == d1 and d2,
                      d1 == d3 and d1 + d3 == d2 and d1,
                  ]
              )
  
          return (
              check(p1, p2, p3)
              and check(p2, p3, p4)
              and check(p1, p3, p4)
              and check(p1, p2, p4)
          )
  
  ############
  
  class Solution(object):
    def validSquare(self, p1, p2, p3, p4):
      """
      :type p1: List[int]
      :type p2: List[int]
      :type p3: List[int]
      :type p4: List[int]
      :rtype: bool
      """
      dist = lambda a, b: ((a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2)
      sideLens = set([dist(p1, p2), dist(p1, p3), dist(p1, p4), dist(p2, p3), dist(p2, p4), dist(p3, p4)])
      if len(sideLens) != 2 or 0 in sideLens:
        return False
      return True
  
  

• func validSquare(p1 []int, p2 []int, p3 []int, p4 []int) bool {
  	check := func(a, b, c []int) bool {
  		x1, y1 := a[0], a[1]
  		x2, y2 := b[0], b[1]
  		x3, y3 := c[0], c[1]
  		d1 := (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2)
  		d2 := (x1-x3)*(x1-x3) + (y1-y3)*(y1-y3)
  		d3 := (x2-x3)*(x2-x3) + (y2-y3)*(y2-y3)
  		if d1 == d2 && d1+d2 == d3 && d1 > 0 {
  			return true
  		}
  		if d1 == d3 && d1+d3 == d2 && d1 > 0 {
  			return true
  		}
  		if d2 == d3 && d2+d3 == d1 && d2 > 0 {
  			return true
  		}
  		return false
  	}
  	return check(p1, p2, p3) && check(p1, p3, p4) && check(p1, p2, p4) && check(p2, p3, p4)
  }
  

• Java
• C++
• Python
• Go

• class Solution {
      public boolean validSquare(int[] p1, int[] p2, int[] p3, int[] p4) {
          if (p1[0] == p2[0] && p1[1] == p2[1])
              return false;
          if (p1[0] == p3[0] && p1[1] == p3[1])
              return false;
          if (p1[0] == p4[0] && p1[1] == p4[1])
              return false;
          if (p2[0] == p3[0] && p2[1] == p3[1])
              return false;
          if (p2[0] == p4[0] && p2[1] == p4[1])
              return false;
          if (p3[0] == p4[0] && p3[1] == p4[1])
              return false;
          int[] distanceSquares = new int[6];
          distanceSquares[0] = distanceSquare(p1, p2);
          distanceSquares[1] = distanceSquare(p1, p3);
          distanceSquares[2] = distanceSquare(p1, p4);
          distanceSquares[3] = distanceSquare(p2, p3);
          distanceSquares[4] = distanceSquare(p2, p4);
          distanceSquares[5] = distanceSquare(p3, p4);
          Arrays.sort(distanceSquares);
          if (distanceSquares[0] != distanceSquares[1] || distanceSquares[1] != distanceSquares[2] || distanceSquares[2] != distanceSquares[3])
              return false;
          else if (distanceSquares[4] != distanceSquares[5])
              return false;
          else
              return true;
      }
  
      public int distanceSquare(int[] p1, int[] p2) {
          return (p2[0] - p1[0]) * (p2[0] - p1[0]) + (p2[1] - p1[1]) * (p2[1] - p1[1]);
      }
  }
  
  ############
  
  class Solution {
      public boolean validSquare(int[] p1, int[] p2, int[] p3, int[] p4) {
          return check(p1, p2, p3) && check(p1, p3, p4) && check(p1, p2, p4) && check(p2, p3, p4);
      }
  
      private boolean check(int[] a, int[] b, int[] c) {
          int x1 = a[0], y1 = a[1];
          int x2 = b[0], y2 = b[1];
          int x3 = c[0], y3 = c[1];
          int d1 = (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
          int d2 = (x1 - x3) * (x1 - x3) + (y1 - y3) * (y1 - y3);
          int d3 = (x2 - x3) * (x2 - x3) + (y2 - y3) * (y2 - y3);
          if (d1 == d2 && d1 + d2 == d3 && d1 > 0) {
              return true;
          }
          if (d1 == d3 && d1 + d3 == d2 && d1 > 0) {
              return true;
          }
          if (d2 == d3 && d2 + d3 == d1 && d2 > 0) {
              return true;
          }
          return false;
      }
  }
  

• // OJ: https://leetcode.com/problems/valid-square/
  // Time: O(1)
  // Space: O(1)
  class Solution {
  private:
      long long dist(vector<int>& a, vector<int>& b) {
          return pow(a[0] - b[0], 2) + pow(a[1] - b[1], 2);
      }
  public:
      bool validSquare(vector<int>& p1, vector<int>& p2, vector<int>& p3, vector<int>& p4) {
          map<long long, int> m;
          vector<vector<int>> v = {p1, p2, p3, p4};
          for (int i = 0; i < 3; ++i) {
              for (int j = i + 1; j < 4; ++j) {
                  auto d = dist(v[i], v[j]);
                  if (!d) return false;
                  m[d]++;
              }
          }
          auto a = *m.begin(), b = *m.rbegin();
          return m.size() == 2 && a.second == 4 && 2 * a.first == b.first;
      }
  };
  

• class Solution:
      def validSquare(
          self, p1: List[int], p2: List[int], p3: List[int], p4: List[int]
      ) -> bool:
          def check(a, b, c):
              (x1, y1), (x2, y2), (x3, y3) = a, b, c
              d1 = (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)
              d2 = (x1 - x3) * (x1 - x3) + (y1 - y3) * (y1 - y3)
              d3 = (x2 - x3) * (x2 - x3) + (y2 - y3) * (y2 - y3)
              return any(
                  [
                      d1 == d2 and d1 + d2 == d3 and d1,
                      d2 == d3 and d2 + d3 == d1 and d2,
                      d1 == d3 and d1 + d3 == d2 and d1,
                  ]
              )
  
          return (
              check(p1, p2, p3)
              and check(p2, p3, p4)
              and check(p1, p3, p4)
              and check(p1, p2, p4)
          )
  
  ############
  
  class Solution(object):
    def validSquare(self, p1, p2, p3, p4):
      """
      :type p1: List[int]
      :type p2: List[int]
      :type p3: List[int]
      :type p4: List[int]
      :rtype: bool
      """
      dist = lambda a, b: ((a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2)
      sideLens = set([dist(p1, p2), dist(p1, p3), dist(p1, p4), dist(p2, p3), dist(p2, p4), dist(p3, p4)])
      if len(sideLens) != 2 or 0 in sideLens:
        return False
      return True
  
  

• func validSquare(p1 []int, p2 []int, p3 []int, p4 []int) bool {
  	check := func(a, b, c []int) bool {
  		x1, y1 := a[0], a[1]
  		x2, y2 := b[0], b[1]
  		x3, y3 := c[0], c[1]
  		d1 := (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2)
  		d2 := (x1-x3)*(x1-x3) + (y1-y3)*(y1-y3)
  		d3 := (x2-x3)*(x2-x3) + (y2-y3)*(y2-y3)
  		if d1 == d2 && d1+d2 == d3 && d1 > 0 {
  			return true
  		}
  		if d1 == d3 && d1+d3 == d2 && d1 > 0 {
  			return true
  		}
  		if d2 == d3 && d2+d3 == d1 && d2 > 0 {
  			return true
  		}
  		return false
  	}
  	return check(p1, p2, p3) && check(p1, p3, p4) && check(p1, p2, p4) && check(p2, p3, p4)
  }
  

All Problems

All Solutions