> For the complete documentation index, see [llms.txt](https://beesec.gitbook.io/algorithms/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://beesec.gitbook.io/algorithms/strings/matrices/valid-square.md).

# Valid Square

{% hint style="info" %}
<https://leetcode.com/problems/valid-square/>
{% endhint %}

{% tabs %}
{% tab title="Question" %}
Given the coordinates of four points in 2D space, return whether the four points could construct a square.&#x20;

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

{% endtab %}

{% tab title="Answer" %}
Let's draw out our square.

![](https://853907954-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MKoQiPsXthu7I640wFl%2F-MLrEQzLS_LbYomYxVAA%2F-MLrFsTEtT_dWYNGnDFI%2Fimage.png?alt=media\&token=109a712e-b449-41cd-a4ec-dddf4005f197)

There are 2 things to note here:

* These numbers do not have to be 0 or 1. They can be 500, 0 etc.
* A valid square has four equal sides with positive length and four equal angles (90-degree angles).

One way to do this is to calculate the number of unique distances. Let's visualise this.

&#x20;

![](https://853907954-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MKoQiPsXthu7I640wFl%2F-MLrEQzLS_LbYomYxVAA%2F-MLrTybaYzBQK3ZgnGpo%2Fimage.png?alt=media\&token=7c45f289-43a4-4187-907e-e4d6fde5d683)

The distance here is 1.

![](https://853907954-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MKoQiPsXthu7I640wFl%2F-MLrEQzLS_LbYomYxVAA%2F-MLrU14aGO2QftVKVTxx%2Fimage.png?alt=media\&token=8c686f5d-64cc-4856-9490-074d4ff27f4b)

And here.\
\
This means for all 4 points, we have 1 unique distance (1 to each point) in this square.

But, if we include diagonals

![](https://853907954-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MKoQiPsXthu7I640wFl%2F-MLrEQzLS_LbYomYxVAA%2F-MLrUHJTfySu3KmPvaX1%2Fimage.png?alt=media\&token=058d271b-e2da-475b-b319-a2430be28c02)

We now have 2.

Using Pythagoras' Therom we can calculate the distance.

We then need to:

* Number of unique distances = 2
* We have 4 distances in total for our square
* We have 2 distances for our diagonals

```python
class Solution(object):
    def validSquare(self, p1, p2, p3, p4):
        points = [p1, p2, p3, p4]
        
        dists = collections.Counter()
        for i in range(len(points)):
            for j in range(i+1, len(points)):
                dists[self.getDistance(points[i], points[j])] += 1
        
        return len(dists.values())==2 and 4 in dists.values() and 2 in dists.values()
        
    def getDistance(self, p1, p2):
        return (p1[0] - p2[0])**2 + (p1[1] - p2[1])**2
```

{% endtab %}
{% endtabs %}