Is Valid Square easy or hard?

Valid Square is rated Medium difficulty. The challenge is recognizing the geometric properties that uniquely define a square and converting them into precise checks using distances or vectors without missing corner cases like duplicate points.

Valid Square Python/Java solution

Python and JavaScript solutions typically use the sorted distance method because it is concise. Java and C++ implementations often demonstrate the vector multiplication approach using dot products and squared magnitudes to confirm perpendicular sides and equal lengths.

How to solve Valid Square in O(n)?

The problem does not scale with input size because exactly four points are provided. All valid solutions run in constant time O(1). Typical implementations compute pairwise squared distances or verify perpendicular vectors using dot products.

What is the best approach for Valid Square?

The sorted distances approach is the most practical solution. Compute the six pairwise squared distances between the four points, sort them, and check that four smallest values are equal sides while the two largest are equal diagonals. The algorithm runs in O(1) time and O(1) space because the number of points is fixed.

Is Valid Square asked at Google/Amazon/Meta?

Geometry validation problems like Valid Square commonly appear in interviews at large tech companies including Amazon, Google, and Meta. They test understanding of distance formulas, vector math, and careful handling of edge cases such as overlapping points.

What data structure is used in Valid Square?

Most solutions only require a small array or list to store pairwise distances between points. The logic mainly relies on geometry calculations such as squared distance and vector dot products rather than complex data structures.

What is the time complexity of Valid Square?

The time complexity is O(1). Only six pairwise distance calculations are required for four points, followed by sorting a constant-size array. Space complexity is also O(1) since only a few variables or a small list of distances are stored.

Description Solution Video 11:25

593. Valid Square

Medium45.5% acceptance3 companies

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

Example 1:

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

Example 2:

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

Example 3:

Input: p1 = [1,0], p2 = [-1,0], p3 = [0,1], p4 = [0,-1]
Output: true

Constraints:

p1.length == p2.length == p3.length == p4.length == 2
-10⁴ <= x_i, y_i <= 10⁴

Asked at 3 companies

Pure Storage Tiktok

Google

Topics

Geometry Math

11:25

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def validSquare(self, p1: List[int], p2: List[int], p3: List[int], p4: List[int]) -> bool:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

[0,0]
[1,1]
[1,0]
[0,1]

Input

[0,0]
[1,1]
[1,0]
[0,12]

Input

[1,0]
[-1,0]
[0,1]
[0,-1]

Your code is saved on this device.Solution