# Valid Square
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/valid-square)
Canonical: https://scaleengineer.com/dsa/problems/valid-square
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Geometry](https://scaleengineer.com/dsa/patterns/geometry)
**Companies:** [Pure Storage](https://scaleengineer.com/companies/pure-storage)
---
## Problem
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`
* `-104 <= xi, yi <= 104`

# Approaches
## Brute Force with Permutations
This approach is based on the idea that since the order of the input points is not guaranteed, we can try all possible configurations of a square. A quadrilateral is defined by the cyclic order of its vertices. For four points, there are three distinct ways to form a quadrilateral, depending on which point is chosen to be diagonally opposite to a fixed point (say, `p1`). We can check each of these three configurations to see if it forms a valid square.
**Time:** O(1) - The number of points is fixed at 4. We perform a constant number of distance calculations and comparisons, regardless of the coordinate values. · **Space:** O(1) - We do not use any auxiliary data structures that scale with input size.
**Pros:** It correctly solves the problem by exhaustively checking all valid geometric configurations.
**Cons:** The logic is more complex than necessary, involving permutations of points which can be tricky to reason about and implement correctly.; It performs more distance calculations than the more optimized approach.
### Explanation
For each of the three possible pairings of diagonals, we check if the resulting quadrilateral is a square. A quadrilateral is a square if all four of its sides are equal in length and its two diagonals are also equal in length. This check ensures both four equal sides (property of a rhombus) and four right angles (property of a rectangle).
We can define a helper function `isSquare(p1, p2, p3, p4)` that assumes `p1, p2, p3, p4` is the cyclic order of vertices. This function calculates the lengths of the four sides (`p1-p2`, `p2-p3`, `p3-p4`, `p4-p1`) and the two diagonals (`p1-p3`, `p2-p4`). If the four sides are equal (and non-zero) and the two diagonals are equal, it's a square.
The main function then calls this `isSquare` function for the three possible cyclic orderings:
1. `(p1, p2, p3, p4)`
2. `(p1, p3, p2, p4)`
3. `(p1, p2, p4, p3)`
If any of these configurations form a square, we return `true`. To avoid floating-point issues, we work with squared distances.
```java
class Solution {
    public boolean validSquare(int[] p1, int[] p2, int[] p3, int[] p4) {
        // Check the 3 possible configurations of a square.
        // The arguments to isSquare are the vertices in cyclic order.
        return isSquare(p1, p2, p3, p4) || 
               isSquare(p1, p3, p2, p4) || 
               isSquare(p1, p2, p4, p3);
    }

    // Checks if p1-p2-p3-p4 form a square in this cyclic order.
    private boolean isSquare(int[] p1, int[] p2, int[] p3, int[] p4) {
        long d12 = distSq(p1, p2);
        long d23 = distSq(p2, p3);
        long d34 = distSq(p3, p4);
        long d41 = distSq(p4, p1);
        
        long diag13 = distSq(p1, p3);
        long diag24 = distSq(p2, p4);

        // Check for non-zero side length, four equal sides, and two equal diagonals.
        return d12 > 0 && d12 == d23 && d23 == d34 && d34 == d41 && diag13 == diag24;
    }

    private long distSq(int[] p1, int[] p2) {
        long dx = p1[0] - p2[0];
        long dy = p1[1] - p2[1];
        return dx * dx + dy * dy;
    }
}
```
### Algorithm
- Define a helper function `distSq(a, b)` to compute the squared distance between two points.
- Define a helper function `isSquare(p1, p2, p3, p4)` that checks if the points form a square in the given cyclic order.
- Inside `isSquare`, calculate the squared lengths of the four sides: `distSq(p1, p2)`, `distSq(p2, p3)`, `distSq(p3, p4)`, `distSq(p4, p1)`.
- Calculate the squared lengths of the two diagonals: `distSq(p1, p3)` and `distSq(p2, p4)`.
- Return `true` if all four side lengths are equal and positive, and the two diagonal lengths are equal.
- In the main function, call `isSquare` for the three possible cyclic orderings of the four points: `(p1, p2, p3, p4)`, `(p1, p3, p2, p4)`, and `(p1, p2, p4, p3)`.
- If any of these calls return `true`, the points form a square. Otherwise, they do not.

## Calculate All Distances and Sort
A more elegant and efficient approach relies on the geometric properties of a square concerning the distances between its vertices. For any four points, there are `4C2 = 6` possible distances between pairs of points. If these points form a square, these 6 distances will consist of four equal side lengths and two equal diagonal lengths. Furthermore, the squared diagonal length will be exactly twice the squared side length (a consequence of the Pythagorean theorem).
**Time:** O(1) - The number of operations is constant. We compute 6 distances, sort a fixed-size array of 6 elements, and perform a few comparisons. · **Space:** O(1) - We use an array of fixed size 6 to store the distances.
**Pros:** Highly efficient with a minimal number of calculations.; The logic is simple, elegant, and robust, as it does not depend on the order of input points.; Less prone to implementation errors compared to permutation-based approaches.
**Cons:** The underlying geometric insight might be slightly less obvious than directly checking geometric configurations.
### Explanation
This method avoids dealing with permutations and orderings explicitly. Instead, we compute all 6 squared distances between the four points and analyze the resulting values.
The algorithm is as follows:
1. Calculate the 6 squared distances between each pair of the four points.
2. Store these 6 values in an array.
3. Sort the array of distances.
After sorting, if the points form a valid square, the array of squared distances must follow a specific pattern: the first four elements must be equal (the squared side length), and the last two elements must be equal (the squared diagonal length).
We then verify the following conditions on the sorted array `d`:
- `d[0] > 0`: This ensures the side length is positive, which implies that no two points are coincident.
- `d[0] == d[1] == d[2] == d[3]`: This confirms that there are four equal sides.
- `d[4] == d[5]`: This confirms that there are two equal diagonals.
- `d[4] == 2 * d[0]`: This verifies the Pythagorean relationship between the side and the diagonal (`diagonal^2 = 2 * side^2`).
If all these conditions are met, the points form a square.
```java
import java.util.Arrays;

class Solution {
    public boolean validSquare(int[] p1, int[] p2, int[] p3, int[] p4) {
        long[] distances = {
            distSq(p1, p2), distSq(p1, p3), distSq(p1, p4),
            distSq(p2, p3), distSq(p2, p4), distSq(p3, p4)
        };

        Arrays.sort(distances);

        // A square has 4 equal sides and 2 equal diagonals.
        // Also, diagonal^2 = 2 * side^2.
        // After sorting, distances[0] to distances[3] should be the sides,
        // and distances[4] to distances[5] should be the diagonals.
        return distances[0] > 0 &&
               distances[0] == distances[1] &&
               distances[1] == distances[2] &&
               distances[2] == distances[3] &&
               distances[4] == distances[5] &&
               distances[4] == 2 * distances[0];
    }

    private long distSq(int[] p1, int[] p2) {
        long dx = p1[0] - p2[0];
        long dy = p1[1] - p2[1];
        return dx * dx + dy * dy;
    }
}
```
### Algorithm
- Define a helper function `distSq(a, b)` to compute the squared distance between two points.
- Create an array to store the 6 squared distances between all unique pairs of the four points.
- Calculate and populate the 6 squared distances.
- Sort the distances array in non-decreasing order.
- Check if the sorted distances satisfy the properties of a square:
    - The smallest distance (side length) must be greater than 0.
    - The first four distances must be equal (four equal sides).
    - The last two distances must be equal (two equal diagonals).
    - The squared diagonal length must be twice the squared side length.
- If all conditions are met, return `true`; otherwise, return `false`.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
class Solution {
public:
  bool validSquare(vector<int> &p1, vector<int> &p2, vector<int> &p3,
                   vector<int> &p4) {
    return check(p1, p2, p3) && check(p1, p3, p4) && check(p1, p2, p4) &&
           check(p2, p3, p4);
  }
  bool check(vector<int> &a, vector<int> &b, vector<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;
  }
};

```

### Python

```python
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))

```