algoadvance

Leetcode 593. Valid Square

Problem Statement

You are given the coordinates of four points in a 2D space. You have to determine if these points can form a square.

A square is a quadrilateral with all sides having equal length and all angles being 90 degrees.

Clarifying Questions

  1. What are the constraints on the coordinates of the points?
    • Coordinates are integers in the range [-10^4, 10^4].
  2. Can the four points be collinear?
    • No, collinear points can’t form a square, so we need to check for this.
  3. Is there any defined order for the points?
    • No, the points can be given in any arbitrary order.

Strategy

  1. Calculate all six distances between the points:
    • Since there are four points, we can calculate 6 unique distances (i.e., the 4 sides and the 2 diagonals of the square).
  2. Identify the unique distances:
    • A square will have exactly two unique distances. The smaller distance should appear exactly 4 times (the sides of the square) and the larger distance should appear exactly 2 times (the diagonals of the square).
  3. Verify the number of occurrences:
    • If the count of the smaller distance is 4 and the count of the larger distance is 2, then the points form a square.

Code

#include <vector>
#include <unordered_set>
#include <cmath>
using namespace std;

class Solution {
public:
    bool validSquare(vector<int>& p1, vector<int>& p2, vector<int>& p3, vector<int>& p4) {
        // Helper function to calculate the squared distance between two points
        auto distSq = [](const vector<int>& a, const vector<int>& b) {
            return (a[0] - b[0]) * (a[0] - b[0]) + (a[1] - b[1]) * (a[1] - b[1]);
        };
        
        unordered_set<int> distances = {
            distSq(p1, p2), distSq(p1, p3), distSq(p1, p4),
            distSq(p2, p3), distSq(p2, p4), distSq(p3, p4)
        };
        
        // A valid square will have exactly 2 unique distances: the sides and the diagonals
        if (distances.size() != 2) return false;
        
        auto side = *distances.begin();
        auto diag = *next(distances.begin());

        // Ensure the smaller value corresponds to sides (it will occur 4 times)
        if (side > diag) swap(side, diag);
        
        int side_cnt = 0, diag_cnt = 0;
        
        // Validate the counts
        vector<vector<int>> points = {p1, p2, p3, p4};
        for (int i = 0; i < points.size(); ++i) {
            for (int j = i + 1; j < points.size(); ++j) {
                int d = distSq(points[i], points[j]);
                if (d == side) side_cnt++;
                else if (d == diag) diag_cnt++;
                else return false; // If any other distance exists, it's not a square
            }
        }
        
        return side_cnt == 4 && diag_cnt == 2;
    }
};

Time Complexity

This solution efficiently checks if the given four points can form a square, ensuring all sides are equal and both diagonals are equal but longer than the sides.

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