Valid Square - Practice Coding Problems

Valid Square - Problem

Math Geometry Medium

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).

Input & Output

Example 1 — Valid Square

$ Input: p1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,1]

› Output: true

💡 Note: The four points form a unit square. All sides have length 1, and both diagonals have length √2.

Example 2 — Invalid Square

$ Input: p1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,12]

› Output: false

💡 Note: The points do not form a square because the sides have different lengths.

Example 3 — Collinear Points

$ Input: p1 = [1,0], p2 = [2,0], p3 = [3,0], p4 = [4,0]

› Output: false

💡 Note: All four points lie on the same line, so they cannot form a square.

Constraints

The coordinates of all four points are integers
-10⁴ ≤ x_i, y_i ≤ 10⁴
All four points are distinct

Visualization

Tap to expand

Understanding the Visualization

Input

Four points in 2D space with coordinates

Process

Calculate distances and verify square properties

Output

Return true if points form a valid square

Key Takeaway

🎯 Key Insight: Check if 6 distances form exactly 4 equal sides and 2 equal diagonals with proper √2 ratio

Asked in

G Google 25 M Microsoft 20 A Apple 15 F Facebook 12

The key insight is that a valid square has exactly 4 equal sides and 2 equal diagonals, with diagonal length = √2 × side length. Best approach is to calculate all 6 distances between points and verify these geometric properties. Time: O(1), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Distance Calculation	O(1)	O(1)	Calculate all 6 distances between points and verify square properties
Center and Side Length Check	O(1)	O(1)	Find center point and verify all points are equidistant with proper angles

Distance Calculation — Algorithm Steps

Calculate all 6 distances between the 4 points
Sort distances to group them
Check if we have exactly 4 equal sides and 2 equal diagonals
Verify diagonal = side × √2

Visualization

Tap to expand

Step-by-Step Walkthrough

Calculate Distances

Find distance between each pair of points

Sort Distances

Arrange distances to identify sides and diagonals

Verify Square

Check if 4 equal sides and 2 equal diagonals with correct ratio

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

long long distanceSquared(int* p1, int* p2) {
    long long dx = p1[0] - p2[0];
    long long dy = p1[1] - p2[1];
    return dx * dx + dy * dy;
}

int compare(const void* a, const void* b) {
    long long la = *(long long*)a;
    long long lb = *(long long*)b;
    if (la < lb) return -1;
    if (la > lb) return 1;
    return 0;
}

int solution(int* p1, int* p2, int* p3, int* p4) {
    int* points[4] = {p1, p2, p3, p4};
    long long distances[6];
    int idx = 0;
    
    // Calculate all 6 distances between 4 points
    for (int i = 0; i < 4; i++) {
        for (int j = i + 1; j < 4; j++) {
            distances[idx++] = distanceSquared(points[i], points[j]);
        }
    }
    
    qsort(distances, 6, sizeof(long long), compare);
    
    // For a valid square: 4 equal sides and 2 equal diagonals
    return (distances[0] == distances[1] && distances[1] == distances[2] && 
            distances[2] == distances[3] && distances[4] == distances[5] &&
            distances[0] > 0 && distances[4] == 2 * distances[0]);
}

void parsePoint(char* line, int* point) {
    char* token = strtok(line, "[,]");
    point[0] = atoi(token);
    token = strtok(NULL, "[,]");
    point[1] = atoi(token);
}

int main() {
    char line[100];
    int p1[2], p2[2], p3[2], p4[2];
    
    fgets(line, sizeof(line), stdin);
    parsePoint(line, p1);
    fgets(line, sizeof(line), stdin);
    parsePoint(line, p2);
    fgets(line, sizeof(line), stdin);
    parsePoint(line, p3);
    fgets(line, sizeof(line), stdin);
    parsePoint(line, p4);
    
    int result = solution(p1, p2, p3, p4);
    printf(result ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(1)

Fixed 4 points means constant number of operations (6 distance calculations)

✓ Linear Growth

Space Complexity

O(1)

Only storing 6 distance values and using constant extra space

✓ Linear Space

32.0K Views

Medium Frequency

~25 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Distance Calculation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler