Jobs

Interviews

Discussions

Valid Square

Medium

Asked by:

6 views

Topics:

ArraysGreedy Algorithms

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 = [1,0], p2 = [-1,0], p3 = [0,1], p4 = [0,-1]
Output: true

Constraints:

p1.length == p2.length == p3.length == p4.length == 2
-10⁴ <= x_i, y_i <= 10⁴

Valid Square

Medium

Asked by:

6 views

Topics:

ArraysGreedy Algorithms

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 = [1,0], p2 = [-1,0], p3 = [0,1], p4 = [0,-1]
Output: true

Constraints:

p1.length == p2.length == p3.length == p4.length == 2
-10⁴ <= x_i, y_i <= 10⁴

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the data type of the coordinates? Can they be floats, or are they strictly integers?
What is the range of possible values for the coordinates? Are negative values allowed?
If the four points do not form a valid square, what should I return? Should I return false, throw an exception, or handle it in some other way?
Are the input points guaranteed to be distinct, or could there be duplicate points in the input?
Is the order of the input points significant? That is, must they be in a specific order, like clockwise or counter-clockwise?

Brute Force Solution

Approach

The problem involves determining if four points in space form a perfect square. A brute force approach involves checking every possible combination of these points to see if they satisfy the properties of a square: equal sides and right angles.

Here's how the algorithm would work step-by-step:

First, calculate the distances between every pair of points. You'll have six distances in total, since you have four points and each point can be paired with three others.
Next, sort these distances from shortest to longest. In a square, you'll have four sides of equal length (shorter distance) and two diagonals of equal length (longer distance).
Check if the four shortest distances are equal, meaning that all four sides are the same length. If they are not equal, then the points cannot form a square.
Check if the two longest distances (diagonals) are equal. If they are not equal, the points cannot form a square.
Finally, ensure that the length of the diagonal is related to the length of the side. Specifically, diagonal length squared should be twice the side length squared (Pythagorean theorem). If it's not, then it's not a square.
If all these conditions are met, then the four points form a valid square.

Code Implementation

def valid_square(point_one, point_two, point_three, point_four):
    def calculate_distance_squared(first_point, second_point):
        return (first_point[0] - second_point[0])**2 + (first_point[1] - second_point[1])**2

    distances = []
    distances.append(calculate_distance_squared(point_one, point_two))
    distances.append(calculate_distance_squared(point_one, point_three))
    distances.append(calculate_distance_squared(point_one, point_four))
    distances.append(calculate_distance_squared(point_two, point_three))
    distances.append(calculate_distance_squared(point_two, point_four))
    distances.append(calculate_distance_squared(point_three, point_four))

    distances.sort()

    # Sides must be of equal length
    if distances[0] == 0 or distances[0] != distances[1] or distances[0] != distances[2] or distances[0] != distances[3]:
        return False

    # Diagonals must be of equal length
    if distances[4] != distances[5]:
        return False

    # Ensure the diagonal squared is twice the side squared
    if distances[4] != 2 * distances[0]:
        return False

    return True

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(1) – The input size is fixed at four points. Calculating the distances between all pairs of points requires a constant number of operations (6 distance calculations). Sorting these distances also takes constant time since there are always six distances. The subsequent checks for side equality, diagonal equality, and the Pythagorean theorem all involve a constant number of comparisons. Therefore, the overall time complexity is O(1) because the number of operations does not depend on a variable input size.

Space Complexity

O(1) – The algorithm calculates six distances between the four points and stores them in a list. This list has a fixed size of 6, regardless of the coordinates of the input points. Sorting this list also happens in place, using a constant amount of extra space. Therefore, the auxiliary space used is constant.

Optimal Solution

Approach

The goal is to determine if four given points form a valid square. The optimal approach focuses on using distances between the points to deduce the properties of a square, avoiding more complex geometric calculations.

Here's how the algorithm would work step-by-step:

First, calculate all six possible distances between the four points. Since we need to find side lengths and diagonal lengths, we need to measure all distances.
Next, organize the distances into a group. We expect to see only two unique distances in a square: the side length and the diagonal length.
Check if there are exactly two unique distances. If not, the points cannot form a square.
Identify the shorter distance. This should represent the side length of the potential square.
Count how many times the shorter distance (side length) appears. It should appear four times, representing the four sides of the square.
Identify the longer distance. This should represent the diagonal length of the potential square.
Count how many times the longer distance (diagonal length) appears. It should appear twice, representing the two diagonals of the square.
Finally, confirm that the longer distance (diagonal length) is equal to the shorter distance (side length) times the square root of 2. This confirms the Pythagorean theorem holds for a square's side and diagonal. If all these conditions are met, the points form a valid square.

Code Implementation

import math

def valid_square(point_one, point_two, point_three, point_four):
    def calculate_distance_squared(point_a, point_b):
        return (point_a[0] - point_b[0])**2 + (point_a[1] - point_b[1])**2

    distances = [
        calculate_distance_squared(point_one, point_two),
        calculate_distance_squared(point_one, point_three),
        calculate_distance_squared(point_one, point_four),
        calculate_distance_squared(point_two, point_three),
        calculate_distance_squared(point_two, point_four),
        calculate_distance_squared(point_three, point_four)
    ]

    unique_distances = set(distances)

    # A square must have exactly two unique distances: side and diagonal.
    if len(unique_distances) != 2:
        return False

    unique_distances = list(unique_distances)
    side_length_squared = min(unique_distances)
    diagonal_length_squared = max(unique_distances)

    # A square has four sides of equal length.
    if distances.count(side_length_squared) != 4:
        return False

    # A square has two diagonals of equal length.
    if distances.count(diagonal_length_squared) != 2:
        return False

    # Diagonal^2 should be twice the side^2 based on Pythagorean theorem.
    if not math.isclose(diagonal_length_squared, 2 * side_length_squared):
        return False

    return True

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(1) – The algorithm calculates the distances between four points. The number of points is fixed (n=4), so the number of distance calculations (6) is also fixed. Organizing these distances, finding unique values, and performing comparisons all take constant time regardless of any input size. Therefore, the time complexity is O(1).

Space Complexity

O(1) – The algorithm calculates six distances and stores them, then organizes them to find unique distances. Regardless of the input points, which is fixed at four, the number of distances calculated and the number of unique distances stored are constant. The space used for storing these distances and related variables does not depend on a variable input size N. Therefore, the space complexity is constant.

Edge Cases

Case	How to Handle
Null or empty input array	Return false immediately since a square requires four distinct points.
Input array contains duplicate points (all four points are the same)	If all points are same, all distances will be zero and the code should return false because a square needs 4 DISTINCT points.
Input array contains three collinear points	If three points are collinear, it is impossible to form a square, so the solution should return false after checking distances or slopes.
Points do not form a square (e.g., a rectangle or rhombus)	The code must explicitly verify the equality of side lengths and diagonal lengths to ensure a square shape and return false if not equal.
Integer overflow when calculating distance (large coordinates)	Use long data type to store the squared distances to prevent integer overflow, ensuring correct distance calculations.
Points provided are not in any particular order	The distance calculation approach is order-independent and correctly identifies distances regardless of input order.
Zero distance between two points (identical coordinates)	The code should check for zero distance between any two points and return false, since a square cannot have overlapping points.
Floating-point precision issues when comparing distances (if using floating point)	Use an epsilon value (small tolerance) when comparing distances to account for potential floating-point inaccuracies.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the data type of the coordinates? Can they be floats, or are they strictly integers?
What is the range of possible values for the coordinates? Are negative values allowed?
If the four points do not form a valid square, what should I return? Should I return false, throw an exception, or handle it in some other way?
Are the input points guaranteed to be distinct, or could there be duplicate points in the input?
Is the order of the input points significant? That is, must they be in a specific order, like clockwise or counter-clockwise?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, calculate the distances between every pair of points. You'll have six distances in total, since you have four points and each point can be paired with three others.
Next, sort these distances from shortest to longest. In a square, you'll have four sides of equal length (shorter distance) and two diagonals of equal length (longer distance).
Check if the four shortest distances are equal, meaning that all four sides are the same length. If they are not equal, then the points cannot form a square.
Check if the two longest distances (diagonals) are equal. If they are not equal, the points cannot form a square.
Finally, ensure that the length of the diagonal is related to the length of the side. Specifically, diagonal length squared should be twice the side length squared (Pythagorean theorem). If it's not, then it's not a square.
If all these conditions are met, then the four points form a valid square.

Code Implementation

def valid_square(point_one, point_two, point_three, point_four):
    def calculate_distance_squared(first_point, second_point):
        return (first_point[0] - second_point[0])**2 + (first_point[1] - second_point[1])**2

    distances = []
    distances.append(calculate_distance_squared(point_one, point_two))
    distances.append(calculate_distance_squared(point_one, point_three))
    distances.append(calculate_distance_squared(point_one, point_four))
    distances.append(calculate_distance_squared(point_two, point_three))
    distances.append(calculate_distance_squared(point_two, point_four))
    distances.append(calculate_distance_squared(point_three, point_four))

    distances.sort()

    # Sides must be of equal length
    if distances[0] == 0 or distances[0] != distances[1] or distances[0] != distances[2] or distances[0] != distances[3]:
        return False

    # Diagonals must be of equal length
    if distances[4] != distances[5]:
        return False

    # Ensure the diagonal squared is twice the side squared
    if distances[4] != 2 * distances[0]:
        return False

    return True

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, calculate all six possible distances between the four points. Since we need to find side lengths and diagonal lengths, we need to measure all distances.
Next, organize the distances into a group. We expect to see only two unique distances in a square: the side length and the diagonal length.
Check if there are exactly two unique distances. If not, the points cannot form a square.
Identify the shorter distance. This should represent the side length of the potential square.
Count how many times the shorter distance (side length) appears. It should appear four times, representing the four sides of the square.
Identify the longer distance. This should represent the diagonal length of the potential square.
Count how many times the longer distance (diagonal length) appears. It should appear twice, representing the two diagonals of the square.
Finally, confirm that the longer distance (diagonal length) is equal to the shorter distance (side length) times the square root of 2. This confirms the Pythagorean theorem holds for a square's side and diagonal. If all these conditions are met, the points form a valid square.

Code Implementation

import math

def valid_square(point_one, point_two, point_three, point_four):
    def calculate_distance_squared(point_a, point_b):
        return (point_a[0] - point_b[0])**2 + (point_a[1] - point_b[1])**2

    distances = [
        calculate_distance_squared(point_one, point_two),
        calculate_distance_squared(point_one, point_three),
        calculate_distance_squared(point_one, point_four),
        calculate_distance_squared(point_two, point_three),
        calculate_distance_squared(point_two, point_four),
        calculate_distance_squared(point_three, point_four)
    ]

    unique_distances = set(distances)

    # A square must have exactly two unique distances: side and diagonal.
    if len(unique_distances) != 2:
        return False

    unique_distances = list(unique_distances)
    side_length_squared = min(unique_distances)
    diagonal_length_squared = max(unique_distances)

    # A square has four sides of equal length.
    if distances.count(side_length_squared) != 4:
        return False

    # A square has two diagonals of equal length.
    if distances.count(diagonal_length_squared) != 2:
        return False

    # Diagonal^2 should be twice the side^2 based on Pythagorean theorem.
    if not math.isclose(diagonal_length_squared, 2 * side_length_squared):
        return False

    return True

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input array	Return false immediately since a square requires four distinct points.
Input array contains duplicate points (all four points are the same)	If all points are same, all distances will be zero and the code should return false because a square needs 4 DISTINCT points.
Input array contains three collinear points	If three points are collinear, it is impossible to form a square, so the solution should return false after checking distances or slopes.
Points do not form a square (e.g., a rectangle or rhombus)	The code must explicitly verify the equality of side lengths and diagonal lengths to ensure a square shape and return false if not equal.
Integer overflow when calculating distance (large coordinates)	Use long data type to store the squared distances to prevent integer overflow, ensuring correct distance calculations.
Points provided are not in any particular order	The distance calculation approach is order-independent and correctly identifies distances regardless of input order.
Zero distance between two points (identical coordinates)	The code should check for zero distance between any two points and return false, since a square cannot have overlapping points.
Floating-point precision issues when comparing distances (if using floating point)	Use an epsilon value (small tolerance) when comparing distances to account for potential floating-point inaccuracies.