Valid Square

Medium
1300.

Valid Square

Valid Square is a medium coding problem on math and geometry, asked in Amazon and Google interviews.

You are given four points p1, p2, p3 and p4 in the plane, each as [x, y] with integer coordinates. They are listed in no particular order.

Return true if the four points are the corners of a square. The square does not have to be aligned with the axes, but it must have positive side length: four sides of equal positive length and four right angles.

Example 1

Input
p1 = [1,0], p2 = [3,1], p3 = [2,3], p4 = [0,2]
Output
true
Explanation
A square tilted by the vector (2,1): every side has squared length 5 and both diagonals have squared length 10.

Example 2

Input
p1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,12]
Output
false

Example 3

Input
p1 = [5,5], p2 = [5,5], p3 = [5,5], p4 = [5,5]
Output
false
Explanation
A single point is not a square.

Constraints

  • p1.length == p2.length == p3.length == p4.length == 2
  • -10^4 <= xi, yi <= 10^4
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} p1
 * @param {number[]} p2
 * @param {number[]} p3
 * @param {number[]} p4
 * @return {boolean}
 */
var validSquare = function(p1, p2, p3, p4) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Valid Square — Solution in Python, Java & C++

Valid Square solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem, asked at Amazon and Google.

Valid Square is a medium coding problem on math and geometry, asked in Amazon and Google interviews.

  • Difficulty: Medium
  • Topics: Math, Geometry
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You are given four points p1, p2, p3 and p4 in the plane, each as [x, y] with integer coordinates. They are listed in no particular order.

Return true if the four points are the corners of a square. The square does not have to be aligned with the axes, but it must have positive side length: four sides of equal positive length and four right angles.

Example 1

Input: p1 = [1,0], p2 = [3,1], p3 = [2,3], p4 = [0,2]
Output: true
Explanation: A square tilted by the vector (2,1): every side has squared length 5 and both diagonals have squared length 10.

Example 2

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

Example 3

Input: p1 = [5,5], p2 = [5,5], p3 = [5,5], p4 = [5,5]
Output: false
Explanation: A single point is not a square.

Constraints

  • p1.length == p2.length == p3.length == p4.length == 2
  • -10^4 <= xi, yi <= 10^4

Hints for Valid Square

  1. Hint 1

    The input order means nothing, so look at all six pairwise distances instead of walking around the shape.

  2. Hint 2

    Squared distances stay integers — never take a square root.

  3. Hint 3

    In a square the four smallest of those six values are equal and positive, and the two largest are equal and exactly twice as big.

How to solve Valid Square

A square is pinned down by its six pairwise distances: four equal sides and two equal diagonals, each diagonal twice the side when squared. Sorting the six squared distances lets you check that without knowing which point is which corner.

Approach

  1. Compute the squared distance for each of the six pairs of points.
  2. Sort the six values.
  3. Return true exactly when the smallest is positive, the first four are equal, the last two are equal, and the last equals twice the first.

Why it works

For a real square the four sides are the four smallest distances and the diagonals (squared length 2s) are the two largest, so the test passes. Conversely, suppose four pairs share the squared length s > 0 and the other two share 2s. The two long pairs cannot share a point — a point at squared distance 2s from two others, with those two at distance s from each other and everything else s, is impossible — so the long pairs are two disjoint 'diagonals' and the short pairs form a closed 4-cycle with equal sides, a rhombus. A rhombus with equal diagonals is a square, and d² = 2s² confirms it.

Complexity

  • Time — O(1)
  • Space — O(1)

Pitfalls

  • Duplicate points give zero distances; insist the smallest squared distance is positive.
  • Checking only 'four equal, two equal' without the factor of 2 is the usual shortcut — it is safe on integer points, but the explicit check costs nothing and does not lean on that fact.
  • Do not assume p1, p2, p3, p4 go around the square in order.

Reference solution

Python

from typing import List

def validSquare(p1: List[int], p2: List[int], p3: List[int], p4: List[int]) -> bool:
    pts = [p1, p2, p3, p4]
    d = []
    for i in range(4):
        for j in range(i + 1, 4):
            dx = pts[i][0] - pts[j][0]
            dy = pts[i][1] - pts[j][1]
            d.append(dx * dx + dy * dy)
    d.sort()
    return d[0] > 0 and d[0] == d[3] and d[4] == d[5] and d[4] == 2 * d[0]

Java

public static boolean validSquare(int[] p1, int[] p2, int[] p3, int[] p4) {
    int[][] pts = { p1, p2, p3, p4 };
    long[] d = new long[6];
    int k = 0;
    for (int i = 0; i < 4; i++) {
        for (int j = i + 1; j < 4; j++) {
            long dx = pts[i][0] - pts[j][0];
            long dy = pts[i][1] - pts[j][1];
            d[k++] = dx * dx + dy * dy;
        }
    }
    Arrays.sort(d);
    return d[0] > 0 && d[0] == d[3] && d[4] == d[5] && d[4] == 2 * d[0];
}

C++

bool validSquare(vector<int>& p1, vector<int>& p2, vector<int>& p3, vector<int>& p4) {
    vector<vector<int>> pts = { p1, p2, p3, p4 };
    vector<long long> d;
    for (int i = 0; i < 4; i++) {
        for (int j = i + 1; j < 4; j++) {
            long long dx = pts[i][0] - pts[j][0];
            long long dy = pts[i][1] - pts[j][1];
            d.push_back(dx * dx + dy * dy);
        }
    }
    sort(d.begin(), d.end());
    return d[0] > 0 && d[0] == d[3] && d[4] == d[5] && d[4] == 2 * d[0];
}

JavaScript

var validSquare = function(p1, p2, p3, p4) {
    var pts = [p1, p2, p3, p4];
    var d = [];
    for (var i = 0; i < 4; i++) {
        for (var j = i + 1; j < 4; j++) {
            var dx = pts[i][0] - pts[j][0];
            var dy = pts[i][1] - pts[j][1];
            d.push(dx * dx + dy * dy);
        }
    }
    d.sort(function(a, b) { return a - b; });
    return d[0] > 0 && d[0] === d[3] && d[4] === d[5] && d[4] === 2 * d[0];
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 337 math problems · the whole catalogue