algoadvance

Leetcode 593. Valid Square

Problem Statement

Given the coordinates of four points in 2D space, determine if the four points can construct a square.

The input is four points in the format (x, y). You need to write a function:

public boolean validSquare(int[] p1, int[] p2, int[] p3, int[] p4)

where p1, p2, p3, and p4 are arrays representing the coordinates of the points.

Clarifying Questions

1. Do all points need to be distinct?
   • Yes, for a valid square, all four points need to be distinct.
2. What if the points form a degenerate square (all points coinciding)?
   • No, if all points coincide, it isn’t considered a square.
3. What range of values can the coordinates of the points take?
   • The coordinates can be any valid integer values within the range of typical integer limits in Java.

Strategy

1. Calculate Distance:
   • Compute the squared distances between all pairs of points.
   • Squared distances are used instead of actual distances to avoid floating-point inaccuracies.
2. Sort and Validate:
   • There should be exactly four smaller distances (the sides of the square) and two larger, equal distances (the diagonals).
   • Specifically: the four sides should be the same and the two diagonals should be the same and larger than the sides.
3. Check the Properties:
   • Verify the uniqueness of points.
   • Verify the correct number of unique distances.

Code

Here is the Java code implementing the above approach:

public class ValidSquare {
    public boolean validSquare(int[] p1, int[] p2, int[] p3, int[] p4) {
        int[] distances = {
            distanceSquared(p1, p2), distanceSquared(p1, p3),
            distanceSquared(p1, p4), distanceSquared(p2, p3),
            distanceSquared(p2, p4), distanceSquared(p3, p4)
        };
        
        Arrays.sort(distances);
        
        // Check that we have 4 sides (equal smaller lengths) and 2 diagonals (equal larger lengths)
        return distances[0] > 0 &&
               distances[0] == distances[1] &&
               distances[0] == distances[2] &&
               distances[0] == distances[3] &&
               distances[4] == distances[5] &&
               distances[4] > distances[3];
    }
    
    private int distanceSquared(int[] a, int[] b) {
        return (a[0] - b[0]) * (a[0] - b[0]) + (a[1] - b[1]) * (a[1] - b[1]);
    }
}

Time Complexity

• Distance Calculation:
  • Calculating the squared distance for 6 pairs of points: (O(1))
• Sorting:
  • Sorting the 6 distances: (O(6 \log 6)) which is effectively (O(1)) given the constant number of elements.

This algorithm runs in constant time (O(1)) since it neither depends on input size (always 4 points) nor complex operations beyond fixed-distance computations and fixed-size sorting.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?