Detect Squares

Medium

Detect Squares

Medium

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 range of values for the coordinates of the points? Can they be negative or non-integer?
If no square can be formed with the given points, what should the count function return?
Will the input consist of only valid coordinates, or should I expect null or invalid input?
Are duplicate points allowed? If so, how should they be handled when counting squares?
How many points can there be at maximum?

Brute Force Solution

Approach

The brute force approach to finding squares from a set of points involves checking every possible combination of points. We try every combination and determine if that combination forms a square. This method guarantees finding all squares, albeit inefficiently.

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

Take any three points from the set of points that we have.
Calculate the distance between each pair of these three points.
Check if any two distances are equal. If no two distances are equal, then these three points cannot form part of a square, so move on to the next set of three points.
If two distances are equal, calculate where the fourth point of the square would need to be. This is done using the coordinates of the first three points.
Check if that fourth point exists in our set of points.
If the fourth point exists, verify that the four points actually form a square (all sides equal and right angles).
If they do, we've found a square; count it. If not, this combination of points doesn't form a square.
Repeat this process for every possible combination of three points in the original set.
The total count of squares found using all combinations is our answer.

Code Implementation

import math

def detect_squares_brute_force(points):
    number_of_points = len(points)
    square_count = 0

    for first_point_index in range(number_of_points):
        for second_point_index in range(first_point_index + 1, number_of_points):
            for third_point_index in range(second_point_index + 1, number_of_points):
                first_point = points[first_point_index]
                second_point = points[second_point_index]
                third_point = points[third_point_index]

                distance_1_2 = calculate_distance(first_point, second_point)
                distance_1_3 = calculate_distance(first_point, third_point)
                distance_2_3 = calculate_distance(second_point, third_point)

                distances = [distance_1_2, distance_1_3, distance_2_3]
                distances.sort()

                if abs(distances[0] - distances[1]) > 1e-6:
                    continue

                # Two sides must be equal to possibly form a square

                possible_fourth_point = calculate_fourth_point(first_point, second_point, third_point)
                
                if possible_fourth_point in points:
                    # Fourth point must actually exist

                    all_points = [first_point, second_point, third_point, possible_fourth_point]
                    if is_valid_square(all_points):
                        square_count += 1

    return square_count

def calculate_distance(point_1, point_2):
    return math.sqrt((point_1[0] - point_2[0])**2 + (point_1[1] - point_2[1])**2)

def calculate_fourth_point(point_1, point_2, point_3):
    # Calculates potential 4th point given 3 others
    x1, y1 = point_1
    x2, y2 = point_2
    x3, y3 = point_3
    
    x4a = x2 + x3 - x1
    y4a = y2 + y3 - y1
    
    x4b = x1 + x3 - x2
    y4b = y1 + y3 - y2
    
    x4c = x1 + x2 - x3
    y4c = y1 + y2 - y3
    
    return (x4a, y4a)

def is_valid_square(points):
    # Validate that all sides are equal and right angles exist
    point_1, point_2, point_3, point_4 = points
    
    distances = [
        calculate_distance(point_1, point_2),
        calculate_distance(point_1, point_3),
        calculate_distance(point_1, point_4),
        calculate_distance(point_2, point_3),
        calculate_distance(point_2, point_4),
        calculate_distance(point_3, point_4)
    ]
    
    distances.sort()
    
    side_length = distances[0]
    diagonal_length = distances[-1]

    if abs(side_length * math.sqrt(2) - diagonal_length) > 1e-6:
        return False
    
    if abs(distances[0] - distances[3]) > 1e-6:
        return False

    return True

Big(O) Analysis

Time Complexity

O(n^3) – The provided brute force algorithm iterates through all possible combinations of three points from a set of n points. Choosing three points from n can be done in n choose 3 ways, which is proportional to n * (n-1) * (n-2). Since calculating the distance between the points and verifying the square properties take constant time, the dominant factor is selecting the combinations. Therefore, the time complexity is proportional to n cubed, which simplifies to O(n^3).

Space Complexity

O(1) – The provided solution's space complexity is determined by the need to store a constant number of variables such as distances between points and coordinates for the potential fourth point of the square. The plain English explanation does not describe the use of any data structures that scale with the number of input points, N. Temporary calculations and variable assignments contribute a constant amount of extra space, irrespective of the input size. Therefore, the auxiliary space used by the algorithm remains constant.

Optimal Solution

Approach

The key is to efficiently count how many points exist for each possible square we can form. We store each point seen so far, and when a new point comes in, we check if it can be a corner of a square with previously seen points. By focusing on finding potential squares instead of checking every possibility, we save time.

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

Remember every point we've seen by storing how many times we've encountered it.
When a new point is added, go through all the points we've already seen to see if any could be diagonal corners of a square with the new point.
For each possible diagonal corner, figure out where the other two corners of the square would be. These corners must form sides parallel to the x and y axes.
Check if we've already seen those other two corners in our memory. If we have, then we've found a square!
Since we know how many times we've seen each corner, multiply those counts together. That tells us how many squares can be formed using this new point.
Don't forget to add the new point to our memory, keeping track of how many times we've seen it.

Code Implementation

class DetectSquares:

    def __init__(self):
        self.pointCounts = {}

    def add(self, point):
        point_string = tuple(point)
        self.pointCounts[point_string] = self.pointCounts.get(point_string, 0) + 1

    def count(self, point):
        count = 0
        point_x, point_y = point

        # Iterate through all points we've seen so far.
        for seen_point, seen_point_count in self.pointCounts.items():
            seen_x, seen_y = seen_point

            # Ensure it can be a diagonal corner of a square.
            if abs(point_x - seen_x) != abs(point_y - seen_y) or (point_x == seen_x or point_y == seen_y):
                continue

            # Calculate the other two potential corners
            other_x1, other_y1 = point_x, seen_y
            other_x2, other_y2 = seen_x, point_y

            other_point1 = (other_x1, other_y1)
            other_point2 = (other_x2, other_y2)

            # Verify the other two corners exist
            if other_point1 in self.pointCounts and other_point2 in self.pointCounts:
                # Multiply counts to get total squares
                count += seen_point_count * self.pointCounts[other_point1] * self.pointCounts[other_point2]

        return count

Big(O) Analysis

Time Complexity

O(n) – The add operation takes O(1) to update the point count. The count operation iterates through all previously added points to find potential diagonal corners, where n is the number of unique points added so far. For each new point, we check at most n previous points. Therefore the time complexity is O(n).

Space Complexity

O(N) – The solution stores each point seen so far, along with its frequency, using a hash map or dictionary. In the worst case, all N input points are unique and must be stored. Therefore, the auxiliary space used by the hash map grows linearly with the number of input points. Consequently, the space complexity is O(N), where N is the number of points added.

Edge Cases

Case	How to Handle
Duplicate points added repeatedly	The count map should increment the count for each repeated point to accurately reflect the frequency of that point, which is important for 'count' calculations.
Points forming very large squares (close to integer overflow during area/distance calculations)	Use long data types to prevent integer overflow during distance or count calculations if the coordinates can result in large intermediate values.
No points have been added prior to a 'count' call	Return 0 if no points have been added because no square can be formed.
Points are added that are collinear and would never form a square	The 'count' method automatically filters out collinear points when it looks for the other two points that would complete a square, as they won't exist at the required coordinates.
Negative coordinates are provided	The solution should handle negative coordinates, as squares can be formed in any quadrant by ensuring correct index access using offsets if necessary and appropriate bounds.
Large number of add operations followed by few count operations	Ensure the memory used by the data structure holding the points scales linearly with the number of added points; consider using a hash map or similar for efficient storage and lookup.
The point to be counted is not in the data structure (x,y)	Return 0 if the given point (x, y) does not exist in the data structure, as it cannot be a corner of any square formed by the existing points.
Points are close to the maximum integer limits which can cause overflow issues.	Use appropriate data types (e.g., long) to handle large coordinates and differences between coordinates to prevent potential overflow during distance or area calculations.