Overflow in intermediate arithmetic
Wrong move: Temporary multiplications exceed integer bounds.
Usually fails on: Large inputs wrap around unexpectedly.
Fix: Use wider types, modular arithmetic, or rearranged operations.
Move from brute-force thinking to an efficient approach using math strategy.
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 pi is represented as [xi, yi]. 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-104 <= xi, yi <= 104Problem summary: 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 pi is represented as [xi, yi]. 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).
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Math
[0,0] [1,1] [1,0] [0,1]
[0,0] [1,1] [1,0] [0,12]
[1,0] [-1,0] [0,1] [0,-1]
Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #593: Valid Square
class Solution {
public boolean validSquare(int[] p1, int[] p2, int[] p3, int[] p4) {
return check(p1, p2, p3) && check(p1, p3, p4) && check(p1, p2, p4) && check(p2, p3, p4);
}
private boolean check(int[] a, int[] b, int[] c) {
int x1 = a[0], y1 = a[1];
int x2 = b[0], y2 = b[1];
int x3 = c[0], y3 = c[1];
int d1 = (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
int d2 = (x1 - x3) * (x1 - x3) + (y1 - y3) * (y1 - y3);
int d3 = (x2 - x3) * (x2 - x3) + (y2 - y3) * (y2 - y3);
if (d1 == d2 && d1 + d2 == d3 && d1 > 0) {
return true;
}
if (d1 == d3 && d1 + d3 == d2 && d1 > 0) {
return true;
}
if (d2 == d3 && d2 + d3 == d1 && d2 > 0) {
return true;
}
return false;
}
}
// Accepted solution for LeetCode #593: Valid Square
func validSquare(p1 []int, p2 []int, p3 []int, p4 []int) bool {
check := func(a, b, c []int) bool {
x1, y1 := a[0], a[1]
x2, y2 := b[0], b[1]
x3, y3 := c[0], c[1]
d1 := (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2)
d2 := (x1-x3)*(x1-x3) + (y1-y3)*(y1-y3)
d3 := (x2-x3)*(x2-x3) + (y2-y3)*(y2-y3)
if d1 == d2 && d1+d2 == d3 && d1 > 0 {
return true
}
if d1 == d3 && d1+d3 == d2 && d1 > 0 {
return true
}
if d2 == d3 && d2+d3 == d1 && d2 > 0 {
return true
}
return false
}
return check(p1, p2, p3) && check(p1, p3, p4) && check(p1, p2, p4) && check(p2, p3, p4)
}
# Accepted solution for LeetCode #593: Valid Square
class Solution:
def validSquare(
self, p1: List[int], p2: List[int], p3: List[int], p4: List[int]
) -> bool:
def check(a, b, c):
(x1, y1), (x2, y2), (x3, y3) = a, b, c
d1 = (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)
d2 = (x1 - x3) * (x1 - x3) + (y1 - y3) * (y1 - y3)
d3 = (x2 - x3) * (x2 - x3) + (y2 - y3) * (y2 - y3)
return any(
[
d1 == d2 and d1 + d2 == d3 and d1,
d2 == d3 and d2 + d3 == d1 and d2,
d1 == d3 and d1 + d3 == d2 and d1,
]
)
return (
check(p1, p2, p3)
and check(p2, p3, p4)
and check(p1, p3, p4)
and check(p1, p2, p4)
)
// Accepted solution for LeetCode #593: Valid Square
struct Solution;
use std::collections::HashSet;
macro_rules! d {
($a:expr, $b:expr) => {
($a[0] - $b[0]) * ($a[0] - $b[0]) + ($a[1] - $b[1]) * ($a[1] - $b[1])
};
}
type Point = Vec<i32>;
impl Solution {
fn valid_square(p1: Point, p2: Point, p3: Point, p4: Point) -> bool {
let mut hs: HashSet<i32> = HashSet::new();
let v: Vec<Point> = vec![p1, p2, p3, p4];
for i in 0..4 {
for j in i + 1..4 {
hs.insert(d!(v[i], v[j]));
}
}
hs.len() == 2 && !hs.contains(&0)
}
}
#[test]
fn test() {
let p1 = vec![0, 0];
let p2 = vec![1, 1];
let p3 = vec![1, 0];
let p4 = vec![0, 1];
let res = true;
assert_eq!(Solution::valid_square(p1, p2, p3, p4), res);
let p1 = vec![0, 0];
let p2 = vec![1, 1];
let p3 = vec![0, 0];
let p4 = vec![0, 0];
let res = false;
assert_eq!(Solution::valid_square(p1, p2, p3, p4), res);
}
// Accepted solution for LeetCode #593: Valid Square
// Auto-generated TypeScript example from java.
function exampleSolution(): void {
}
// Reference (java):
// // Accepted solution for LeetCode #593: Valid Square
// class Solution {
// public boolean validSquare(int[] p1, int[] p2, int[] p3, int[] p4) {
// return check(p1, p2, p3) && check(p1, p3, p4) && check(p1, p2, p4) && check(p2, p3, p4);
// }
//
// private boolean check(int[] a, int[] b, int[] c) {
// int x1 = a[0], y1 = a[1];
// int x2 = b[0], y2 = b[1];
// int x3 = c[0], y3 = c[1];
// int d1 = (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
// int d2 = (x1 - x3) * (x1 - x3) + (y1 - y3) * (y1 - y3);
// int d3 = (x2 - x3) * (x2 - x3) + (y2 - y3) * (y2 - y3);
// if (d1 == d2 && d1 + d2 == d3 && d1 > 0) {
// return true;
// }
// if (d1 == d3 && d1 + d3 == d2 && d1 > 0) {
// return true;
// }
// if (d2 == d3 && d2 + d3 == d1 && d2 > 0) {
// return true;
// }
// return false;
// }
// }
Use this to step through a reusable interview workflow for this problem.
Simulate the process step by step — multiply n times, check each number up to n, or iterate through all possibilities. Each step is O(1), but doing it n times gives O(n). No extra space needed since we just track running state.
Math problems often have a closed-form or O(log n) solution hidden behind an O(n) simulation. Modular arithmetic, fast exponentiation (repeated squaring), GCD (Euclidean algorithm), and number theory properties can dramatically reduce complexity.
Review these before coding to avoid predictable interview regressions.
Wrong move: Temporary multiplications exceed integer bounds.
Usually fails on: Large inputs wrap around unexpectedly.
Fix: Use wider types, modular arithmetic, or rearranged operations.