Introduction to Math and Geometry

About the pattern

The Math and Geometry pattern focuses on coding problems involving mathematical concepts, geometric properties, and coordinate systems. These challenges often require analyzing numbers, points, lines, angles, and shapes in 2D or 3D space. A strong command of this pattern helps you tackle tasks related to distances, areas, and coordinate-based computations.

Some of the core topics under this pattern are listed below:

• Elementary number theory: This focuses on integer properties and relationships. For example:

  • Greatest common divisor (GCD): To calculate the GCD of two numbers $a$ and $b$, repeatedly apply $gcd(a,b)=gcd(b,a \mod b)$ until $b=0$. The final non-zero value of $a$ is the greatest common divisor. This method is known as Euclid’s algorithm.

  • Least common multiple (LCM): The LCM of two numbers can be calculated as: $lcm(a,b) = \dfrac{a \times b}{\gcd(a, b)}$.

• Advanced integer handling: This concept involves manipulating integers that may push the limits of standard integer data type, such as adding or multiplying large numbers or reversing integers.

  • These operations are often performed digit by digit to avoid overflow and ensure precision.

• Distance between points: This focuses on calculating how far apart two points are on a 2D plane.

  • For two points, $(x_1, y_1)$ and $(x_2, y_2)$, the distance can be calculated using:

    • Euclidean distance: $\sqrt{(x_2​−x_1​)^2+(y_2​−y_1​)^2}$

    • Manhattan distance: $|x_2​−x_1|+|y_2​−y_1​|$

• Slope calculation: This concept covers measuring the steepness of a line between two points, paying attention to vertical lines.

  • For two points, $(x_1, y_1)$ and $(x_2, y_2)$, the slope is calculated as: $m = \dfrac{(y2​−y1​)​}{(x2​−x1​)}$.

    • Special care is needed when $x_2 = x_1$ (i.e., a vertical line).

• Angle measurement: This involves computing angles between lines or points, often using the inverse tangent function.

  • Using $arctan$: The angle is calculated as $θ=arctan(\dfrac{​y2​−y1}{x2​−x1}​​)$.

  • Using $atan2$: The angle is computed as $θ=atan2(y2​−y1​,x2​−x1​)$

    • This method is preferred as it properly handles all quadrants and avoids division by zero errors.

• Polygon geometric attributes: This focuses on calculating side lengths, angles (interior or exterior), area, and perimeter for polygons.

• Polygon spatial attributes: This involves verifying polygon properties such as convexity or orientation.

  • Convexity check: Use the sign of the cross product for every trio of consecutive vertices to ensure all interior angles are less than $180 \degree$.

  • Orientation: Check the clockwise or counterclockwise order of vertices using the sign of the cross product.

• Validate polygons: This focuses on determining if a set of points forms a valid polygon, such as a triangle or square.

  • For example, a square requires:

    • All four sides are equal.

    • Both diagonals are equal.

Beyond applying these mathematical concepts, this pattern also emphasizes the importance of algorithmic efficiency. A brute force approach might require evaluating all combinations of numbers, points, or shapes—potentially leading to high computational costs. Recognizing and applying optimal techniques, such as the two-pointer approach, can significantly reduce runtime and make solutions far more effective.

Examples

The following examples illustrate some problems that can be solved with this approach:

• Check If It Is a Straight Line: Given an array of coordinates where each element represents a point in the XY plane, determine whether all the points lie on the same straight line in the XY plane.