Four Stakes Make a Square

MediumMath & Geometry

Problem

A surveyor drives four stakes into the ground at integer coordinates, given in no particular order as points[i] = [x, y].

Return true if the four stakes are the corners of a square with positive side length (the square may be tilted at any angle), otherwise false.

Example 1

Input:
points = [[0, 0], [1, 1], [1, 0], [0, 1]]
Output:
true

Example 2

Input:
points = [[0, 0], [2, 1], [3, 3], [1, 2]]
Output:
false

All four sides have length √5, but the diagonals differ: this is a rhombus, not a square.

Example 3

Input:
points = [[0, 0], [3, 1], [2, 4], [-1, 3]]
Output:
true

A tilted square with side √10.

Constraints

  • points.length = 4
  • -10^4 ≤ x, y ≤ 10^4

Hint

Show the first hint

Four points have six pairwise distances. What do those six look like for a square?

Walkthrough

How to approach it

01Clarify before coding

  • Are the points given in order around the square? No, any order.
  • Can points repeat? Yes, and then it is not a square because the side must be positive.
  • Can the square be rotated? Yes, so checking axis alignment is not enough.

02Brute force

Try all 24 orderings of the points as a quadrilateral and check equal sides and right angles with dot products.

Cost: O(1) as well, but with many cases and easy mistakes around orientation.

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.