To solve Valid Square, quickly compute all pairwise distances and validate that exactly two distinct distances exist. Ensure the smaller distance occurs four times for sides and the larger distance occurs twice for diagonals. Confirm no points coincide and all angles are right using the distance pattern, enabling a fast geometric validation of a square.
Problem Statement
You are given four points in 2D space represented as p1, p2, p3, and p4. Each point pi has coordinates [xi, yi]. Determine whether these four points can form a valid square regardless of their order.
A valid square must have four sides of equal positive length and four 90-degree angles. Return true if the points construct such a square, and false otherwise.
Examples
Example 1
Input: p1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,1]
Output: true
Example details omitted.
Example 2
Input: p1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,12]
Output: false
Example details omitted.
Example 3
Input: p1 = [1,0], p2 = [-1,0], p3 = [0,1], p4 = [0,-1]
Output: true
Example details omitted.
Constraints
- p1.length == p2.length == p3.length == p4.length == 2
- -104 <= xi, yi <= 104
Solution Approach
Compute Pairwise Distances
Calculate the squared distances between every pair of points to avoid floating-point errors. Use these distances to identify potential side lengths and diagonals, which is critical because miscalculating distances can falsely indicate a non-square.
Validate Side and Diagonal Counts
Count the frequency of each unique distance. A valid square should have exactly two distinct distances: the smaller one occurring four times for sides and the larger one occurring twice for diagonals. Any deviation immediately rules out a square.
Check for Coinciding Points and Geometry Consistency
Ensure no two points coincide and that the diagonal length is consistent with the side length using the Pythagorean relationship. This step prevents false positives from rectangles or degenerate quadrilaterals.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | Depends on the final approach |
| Space | Depends on the final approach |
Time complexity is O(1) because there are always six pairwise distances to compute regardless of input. Space complexity is also O(1) for storing distances and their counts.
What Interviewers Usually Probe
- Are all points guaranteed to be distinct and in integer coordinates?
- Should we handle floating-point errors or stick to integer arithmetic?
- Do we need to verify 90-degree angles explicitly or infer from side and diagonal lengths?
Common Pitfalls or Variants
Common pitfalls
- Failing to check that all four sides are positive and equal length.
- Assuming the input order represents any specific sequence of vertices.
- Using square roots instead of squared distances, causing floating-point inaccuracies.
Follow-up variants
- Check if four points form a rectangle instead of a square, focusing on opposite sides equality.
- Determine if N points can form a regular polygon using generalized distance patterns.
- Validate if four points form a rhombus by verifying equal side lengths but not necessarily right angles.
How GhostInterview Helps
- Automatically computes pairwise distances and highlights discrepancies in side and diagonal counts.
- Provides step-by-step vector and geometric validation to avoid common mistakes in angle checks.
- Identifies degenerate or coinciding points to prevent false positives before final evaluation.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
FAQ
What defines a valid square in the Valid Square problem?
A valid square requires four equal-length sides with positive length and four right angles, independent of point order.
Why compute squared distances instead of actual distances?
Squared distances avoid floating-point errors and maintain integer arithmetic, making side and diagonal comparisons exact.
How can I distinguish a square from a rectangle here?
By counting distance frequencies: squares have exactly four equal sides and two equal diagonals, whereas rectangles have two equal sides and two equal diagonals.
Do the input points need to be in any specific order?
No, the solution must handle any input order by considering all pairwise distances and validating the square geometry.
Can coinciding points form a valid square?
No, any coinciding points mean side lengths are zero, which violates the positive-length requirement for a square.
Need direct help with Valid Square instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Valid Square from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Find the perimeter fence of a garden by determining the outermost trees in a set of given tree coordinates.
Open problem page#478 Generate Random Point in a CircleGenerate Random Point in a Circle requires creating a uniform random point inside a circle using math and geometry principles efficiently.
Open problem page#391 Perfect RectangleDetermine if given axis-aligned rectangles form a perfect cover using array scanning and hash-based corner counting techniques.
Open problem page