Valid Square - Complete Solution Guide

Valid Square is LeetCode problem 593, a Medium level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

Given the coordinates of four points in 2D space p1 , p2 , p3 and p4 , return true if the four points construct a square . The coordinate of a point p i is represented as [x i , y i ] . The input is not given in any order. A valid square has four equal sides with positive length and four equal angles (90-degree angles). Example 1: Input: p1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,1] Output: true Example 2: Input: p1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,12] Output: false Example 3: Input: p1

Detailed Explanation

The problem asks us to determine whether four given points in a 2D plane form a valid square. A valid square must have four equal sides, all angles must be 90 degrees, and the area must be greater than zero (i.e., the points can't all be the same). The input consists of four coordinate pairs, p1, p2, p3, and p4, where each coordinate is an integer. The order of the input points is not specified. The output should be `true` if the four points form a square, and `false` otherwise.

Solution Approach

The solution calculates the squared distances between all six pairs of points. It then sorts these distances in ascending order. If the points form a square, the four smallest distances will be equal (sides), the two largest distances will be equal (diagonals), each side's length must be positive and the square of the diagonal length must be twice the square of the side length. The solution checks these conditions. Using squared distances avoids floating-point precision issues that can arise when calculating actual distances using square roots.

Step-by-Step Algorithm

1. Step 1: Define a function `dist_sq(pt1, pt2)` to calculate the squared distance between two points.
2. Step 2: Calculate the squared distances between all six pairs of points (p1, p2), (p1, p3), (p1, p4), (p2, p3), (p2, p4), and (p3, p4) and store them in a list or array.
3. Step 3: Sort the distances in ascending order.
4. Step 4: Check if the smallest distance is greater than zero (to ensure that no two points are the same).
5. Step 5: Check if the first four distances are equal (four equal sides).
6. Step 6: Check if the last two distances are equal (two equal diagonals).
7. Step 7: Check if the square of diagonal's length is twice of the square of side's length (dists[4] == 2 * dists[0]).
8. Step 8: Return `true` if all the above conditions are met, otherwise return `false`.

Key Insights

• Insight 1: To determine if the four points form a square, we can calculate all six pairwise distances between the points. In a square, there are four sides of equal length and two diagonals of equal length. The diagonal length is sqrt(2) times the side length, so the square of the diagonal length is twice the square of the side length.
• Insight 2: If any of the calculated distances is zero, it means two or more points are coincident, and therefore it cannot be a valid square.
• Insight 3: Sorting the distances allows us to easily compare the four shortest distances (sides) and the two longest distances (diagonals). This avoids complex calculations like checking if the diagonals bisect each other at right angles.

Complexity Analysis

Time Complexity: O(1)

Space Complexity: O(1)

Topics

This problem involves: Math, Geometry.

Companies

Asked at: Pure Storage.