593. Valid Square

Problem Description

The problem requires determining whether four given points in a 2D plane form a square. The input includes the coordinates of each point, and the points are not necessarily given in any specific order. A valid square must have all four sides of equal length, and all four angles must be right angles (90 degrees). The task is to return true if the points form a valid square and false otherwise.

Intuition

To solve this problem, the intuition is to check every possible combination of three points out of the four to form two sides of a square and then calculate the lengths of these sides using the distance formula. The key idea is that for any three points which form a right angle, two sides squaring and adding them up should give the square of the third side (following the Pythagorean theorem). This condition should be true for all combinations of three points. This ensures that four right angles are formed. Moreover, the lengths of adjacent sides should be equal (and greater than zero to avoid degenerate cases).

The solution consists of a check function which performs the calculations and comparisons. It calculates the squared distances between pairs of points (d1, d2, d3) and checks for the two conditions: equality of any two distances to make sure the sides are equal, and the sum of these two equal distances should be equal to the third distance, ensuring a 90-degree angle between them. It also checks that the distance is non-zero to avoid considering points that overlap as valid sides.

The solution verifies these conditions for all combinations of three points out of the four: (p1, p2, p3), (p2, p3, p4), (p1, p3, p4), and (p1, p2, p4). If all combinations satisfy the condition, we conclude that the points can form a valid square.

Learn more about Math patterns.

Solution Approach

The implementation of the solution employs the concept of distance calculation between points and the comparison of these distances to validate the square's sides and angles. Here's how the approach unfolds step by step:

1. Distance Formula: To calculate the squared distance between two points (x1, y1) and (x2, y2) in 2D space, we use the distance formula (x1 - x2)² + (y1 - y2)². We avoid the square root computation for efficiency and because it can introduce floating-point precision issues. Squared distances are sufficient for comparison purposes.

2. Check Function: This helper function check takes three points a, b, and c as arguments and calculates the squared distances between them: d1 is the distance between a and b, d2 is the distance between a and c, and d3 is the distance between b and c.

3. Right Angle Validation: Inside the check function, it checks if any pair of these distances (d1, d2, d3) are equal – indicating that two sides of a triangle formed by the points are equal – and if the sum of their squares equals the square of the third distance. This is essentially checking for a right triangle using the Pythagorean theorem.

4. Non-zero Sides: The check function also ensures that the distances are non-zero to prevent considering points that are the same (overlap) as valid sides of a square.

5. Combining Checks: The validSquare method calls the check function for all combinations of three points out of the four points given. This step is crucial as it verifies the square property from all angles and sides.

The input is in the form of four points p1, p2, p3, and p4, each represented as a list of two integers.

The check is written in Python as:

1def check(a, b, c):
2    (x1, y1), (x2, y2), (x3, y3) = a, b, c
3    d1 = (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)
4    d2 = (x1 - x3) * (x1 - x3) + (y1 - y3) * (y1 - y3)
5    d3 = (x2 - x3) * (x2 - x3) + (y2 - y3) * (y2 - y3)
6    return any([
7        d1 == d2 and d1 + d2 == d3 and d1,
8        d2 == d3 and d2 + d3 == d1 and d2,
9        d1 == d3 and d1 + d3 == d2 and d1,
10    ])

The final return statement calls the check function multiple times to verify each three-point combination forms part of a square:

1return (
2    check(p1, p2, p3) and check(p2, p3, p4) and check(p1, p3, p4) and check(p1, p2, p4)
3)

Overall, the provided Python solution leverages simple geometry and efficient calculations without the need for complex data structures or algorithms. It is an elegant example of applying mathematical principles to solve a computational problem.

Example Walkthrough

Let's walk through the solution approach with a small example. Suppose we have the following four points that are potential vertices of a square:

• p1 = (1, 1),
• p2 = (1, 3),
• p3 = (3, 1),
• p4 = (3, 3).

These points are given in no specific order and might form a square in a 2D plane. We will use the functions and approach described in the solution to determine if these points make up a valid square.

First, the distance formula is used to check if the sides formed by these points are equal, and if the diagonals intersect at a right angle. Squared distances are calculated as follows:

• d1 (distance between p1 and p2): $(1 - 1)^2 + (1 - 3)^2 = 0 + 4 = 4`
• d2 (distance between p1 and p3): $(1 - 3)^2 + (1 - 1)^2 = 4 + 0 = 4`
• d3 (distance between p2 and p3): $(1 - 3)^2 + (3 - 1)^2 = 4 + 4 = 8`

The helper function check now verifies if two distances are equal and if the sum of their squares equals the third distance. For our distances, we have:

• d1 equals d2, and d1 + d2 equals d3. We also ensure d1 is non-zero which it is. This combination reflects two equal sides of a triangle and a right angle between them.

We will repeat this process for the other combinations of points:

• When checking p2, p3, and p4, we obtain d1 = 4, d2 = 4, and d3 = 8, satisfying the conditions.
• For p1, p3, and p4, we compute d1 = 4, d2 = 4, and d3 = 8 again, meeting the conditions.
• Lastly, for p1, p2, and p4, we find d1 = 4, d2 = 4, and d3 = 8, which also passes the check.

Each combination gives us two equal sides and a diagonal that conforms to the Pythagorean theorem, indicating four right angles in total. Since the points p1, p2, p3, and p4 satisfy the check for every combination, they form a valid square, and the function would return true.

To summarize, the solution involves using the distance formula to calculate squared distances between different points, followed by an application of the Pythagorean theorem to ensure right angles and equal sides. This simple yet effective solution illustrates how mathematical principles can be used to solve computational geometry problems.

Solution Implementation

Time and Space Complexity

The given Python code defines a method validSquare to check whether four points form a valid square.

Time Complexity:

To analyze the time complexity, we'll consider the significant operations in the given code.

1. The check function calculates the distances squared (to avoid floating point arithmetic) for three pairs of points. This requires a constant amount of operations, specifically, six subtractions and six multiplications for the distance calculations, plus comparisons and additions. So the time complexity for this part is O(1).

2. The validSquare method calls the check function four times, once for each combination of three points out of four. Since the number of calls to check does not depend on the input size (it's always four), this also contributes a constant factor.

There are no loops or recursive calls that depend on the size of the input, hence the overall time complexity is O(1).

Space Complexity:

Now let's examine the space complexity.

1. The check function uses a fixed amount of space for variables to store the distances and the points. No additional data structures that grow with input size are used, so its space complexity is O(1).

2. The main validSquare method does not use any additional space apart from the space required for the check function and the input points.

Therefore, the space complexity is O(1).

In summary:

• The time complexity of the code is O(1).
• The space complexity of the code is O(1).

Learn more about how to find time and space complexity quickly using problem constraints.