aloalgoDistance and Orientation
This section covers the geometry patterns you'll encounter in top interview problems: distance calculations, rectangle operations, and point validation.Distance Formulas
Different distance metrics are useful for different problems.| Distance Type | Formula | Use Case |
|---|---|---|
| Euclidean | sqrt((x2-x1)² + (y2-y1)²) | Real-world distance |
| Squared Euclidean | (x2-x1)² + (y2-y1)² | Comparing distances (faster) |
| Manhattan | |x2-x1| + |y2-y1| | Grid movement (no diagonals) |
K Closest Points to Origin
A classic interview problem: find the K points closest to the origin. Use squared distance with a max-heap of size K for O(n log k) time.Rectangle Overlap
Rectangles are typically represented as [x1, y1, x2, y2] where (x1, y1) is the bottom-left corner and (x2, y2) is the top-right corner. Two rectangles overlap if their projections overlap on both axes.Valid Square
Given four points, determine if they form a valid square. A square has four equal sides and two equal diagonals (where diagonal = side * sqrt(2)).Rotate Image (Matrix Rotation)
A classic interview problem: rotate an n×n matrix 90 degrees clockwise in-place. The key insight is that rotation = transpose + reverse each row.Layer-by-Layer Rotation
An alternative approach rotates elements in groups of 4, moving from outer layers inward. This directly swaps elements without extra steps.Key Takeaways
- Use squared distance when comparing distances to avoid expensive sqrt operations
- K Closest Points: Use a max-heap of size K for O(n log k) time complexity
- Rectangle overlap: Check if projections overlap on both X and Y axes, or equivalently check for no-overlap conditions
- Valid square: Calculate all 6 pairwise distances and verify 4 equal sides + 2 equal diagonals
- Matrix rotation: 90° clockwise = transpose + reverse rows; counter-clockwise = reverse rows + transpose
Was this helpful?
Company
Practice
© 2026 aloalgo. All rights reserved.