Determine whether points form squares
Company: Purestorage
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
## Problem: Square detection and counting from point coordinates
You are given points on a 2D plane with integer coordinates.
### Part A — Validate a single square
Given **exactly 4 points** `[(x1,y1), (x2,y2), (x3,y3), (x4,y4)]`, determine whether these 4 points can be the vertices of a **non-degenerate square** (square may be rotated; sides are not necessarily axis-aligned).
**Output:** `true` if they form a square, otherwise `false`.
### Part B — Count squares in a set (with optimization)
Given **N points** (may contain duplicates; treat duplicates as separate inputs but they should not create degenerate “squares”), count how many **distinct squares** can be formed whose **4 vertices are all present in the set**.
- A square is considered the same regardless of the order of its vertices.
- Squares may be rotated.
**Follow-up:**
1. Describe a brute-force approach (e.g., around \(O(n^4)\)).
2. Improve it to about \(O(n^3)\).
3. Further improve to about \(O(n^2)\) time (assume hash set / hash map lookups are \(O(1)\) average).
### Constraints (assume typical interview constraints)
- `1 <= N <= 2e4` (for the optimized discussion)
- Coordinates fit in 32-bit signed integers
Clarify any additional assumptions you need (e.g., whether duplicates should be ignored by converting to a set).
Quick Answer: This question evaluates computational geometry, combinatorial counting, and algorithmic optimization skills by requiring validation of a non-degenerate square from four 2D integer points and counting distinct squares in a larger point set, and it falls under the Coding & Algorithms category.
Validate a Single Square
You are given exactly 4 points on a 2D plane with integer coordinates as a list `points = [[x1,y1],[x2,y2],[x3,y3],[x4,y4]]`.
Determine whether these 4 points can be the vertices of a **non-degenerate square**. The square may be rotated (sides are not necessarily axis-aligned). A set of points where two or more coincide, or where the points are collinear, is **not** a valid square.
Return `true` if they form a square, otherwise `false`.
**Approach hint:** Compute all 6 pairwise squared distances. A square has exactly 4 equal smallest distances (the sides) and 2 equal largest distances (the diagonals), where diagonal² = 2 × side², and side² must be greater than 0. Using *squared* distances keeps everything in integer arithmetic and avoids floating-point error.
Constraints
- Exactly 4 points are provided.
- Coordinates fit in 32-bit signed integers.
- Coincident points or collinear points do not form a square.
- The square may be rotated (not necessarily axis-aligned).
Examples
Input: [[0,0],[0,1],[1,1],[1,0]]
Expected Output: True
Explanation: Unit axis-aligned square.
Input: [[0,0],[2,1],[3,-1],[1,-2]]
Expected Output: True
Explanation: Rotated square with side² = 5 and diagonal² = 10.
Hints
- Avoid floating point: compare *squared* distances so all math stays in integers.
- Collect all 6 pairwise squared distances and sort them.
- A valid square: the 4 smallest are equal (sides, > 0) and the 2 largest are equal and equal to 2× the side² (diagonals).
Count Squares in a Point Set
You are given `N` points on a 2D plane with integer coordinates as a list `points = [[x,y], ...]`. The input may contain duplicate coordinates; duplicates should be collapsed (they cannot help form a square).
Count how many **distinct squares** can be formed whose **4 vertices are all present in the set**. A square is the same regardless of the order of its vertices, and squares may be rotated.
**Optimization story (this is exactly the interview follow-up):**
- Brute force: try every 4-tuple of points and test if they form a square — about `O(n^4)`.
- Better: fix one side (a pair of points) and derive the other two vertices — about `O(n^3)`.
- Best (implemented here): iterate over every **pair of points treated as a diagonal**, derive the other two vertices via the perpendicular-diagonal formula, and check membership in a hash set — about `O(n^2)` with O(1) average lookups. Each square is discovered via both of its diagonals, so divide the final count by 2.
Given a diagonal with endpoints `(x1,y1)` and `(x2,y2)`, the other two vertices are `((x1+x2 + y1-y2)/2, (y1+y2 + x2-x1)/2)` and `((x1+x2 - y1+y2)/2, (y1+y2 - x2+x1)/2)`. They count only when those coordinates are integers and both are present in the set.
Constraints
- 1 <= N <= 2e4 for the optimized discussion.
- Coordinates fit in 32-bit signed integers.
- Duplicate coordinates are collapsed and cannot form a square.
- A square counts once regardless of vertex order; rotated squares count.
Examples
Input: [[0,0],[0,1],[1,1],[1,0]]
Expected Output: 1
Explanation: A single unit square.
Input: [[0,0],[0,1],[1,1],[1,0],[2,0],[2,1]]
Expected Output: 2
Explanation: A 2x3 grid of points forms two adjacent unit squares.
Hints
- Put all distinct points in a hash set for O(1) average membership tests.
- Treat each pair of points as a diagonal of a candidate square; the perpendicular bisector of equal length gives the other two vertices.
- Derived vertex coordinates may be non-integer (half values) — skip those (a real lattice square would land on integer coordinates).
- Each square has two diagonals, so it is counted twice — divide the total by 2.