Welcome to Subscribe On Youtube
  • 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)
    }
    
  • 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