Katkat
Back

Count Squares from Points in the Plane

6SenseSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to efficiently store spatial coordinates and leverage geometric properties (like midpoints or diagonals) to detect squares within a 2D plane.

Problem Statement

Given a set of 2D coordinates points represented as a list of (x, y) tuples, write a function count_squares(points) that returns the total number of squares that can be formed using any four points from the given set. Assume that the edges of the squares do not necessarily have to be parallel to the x and y axes.

Function Signature

def count_squares(points: List[Tuple[int, int]]) -> int:

Examples

Example 1: Input: points = [(0,0), (1,0), (0,1), (1,1)] Output: 1 Explanation: These four points form a single square.

Example 2: Input: points = [(0,0), (1,1), (2,0), (1,-1)] Output: 1 Explanation: These points form a square rotated by 45 degrees.

Constraints

  • n (number of points) is in the range [0, 500].
  • Coordinates are integers between -1000 and 1000.
  • A square must have four distinct points.

Considerations

  • Focus on an efficient lookup strategy to avoid an O(n^4) brute-force search.
  • Consider how to uniquely identify a square to avoid double counting.

Hints

Hint 1

Storing all points in a hash set allows for O(1) existence checks.

Hint 2

A square can be uniquely defined by two points that form a diagonal; can you derive the coordinates of the other two corners using these two points?

Hint 3

If you iterate over every pair of points and treat them as a potential diagonal, ensure you are only counting each square once.

Follow-up questions

  • What is the time complexity of your solution, and can it be optimized further if the coordinates are very large?
  • How would your approach change if we only needed to count squares that are axis-aligned (edges parallel to x and y axes)?
  • How would you modify the function to return the actual coordinates of the squares found instead of just the count?