DDSA Solutions

593. Valid Square

MediumView on LeetCode
ArrayMathGeometry
Time: O(1)
Space: O(1)

Problem Overview

Four points form a square if the 6 pairwise distances have exactly 2 distinct values: 4 equal sides and 2 equal diagonals, with diagonal� = 2 � side�.

Intuition

Four points form a square if the 6 pairwise distances have exactly 2 distinct values: 4 equal sides and 2 equal diagonals, with diagonal� = 2 � side�.

Algorithm

  1. 1Compute all 6 pairwise squared distances.
  2. 2Sort them. The first 4 should be equal (sides) and last 2 equal (diagonals).
  3. 3Verify sides > 0 and diagonals = 2 � sides.

Common Pitfalls

  • •Use squared distances (int) to avoid floating-point issues. Reject degenerate cases where min distance is 0.
593.cs
C#
// Approach: Compute all 6 pairwise squared distances; a valid non-degenerate
// square has exactly 2 distinct values (4 equal sides + 2 equal diagonals).
// Time: O(1) Space: O(1)

public class Solution
{
    public bool ValidSquare(int[] p1, int[] p2, int[] p3, int[] p4)
    {
        HashSet<int> distSet = new HashSet<int>();
        int[][] points = { p1, p2, p3, p4 };

        for (int i = 0; i < 4; ++i)
        {
            for (int j = i + 1; j < 4; ++j)
                distSet.Add(Dist(points[i], points[j]));
        }

        return !distSet.Contains(0) && distSet.Count == 2;
    }

    private int Dist(int[] p1, int[] p2)
    {
        return (p1[0] - p2[0]) * (p1[0] - p2[0]) + (p1[1] - p2[1]) * (p1[1] - p2[1]);
    }
}
Was this solution helpful?

Related Problems