812. Largest Triangle Area

Time: O(n³)

Space: O(1)

Approach

Brute-force all O(n³) triples of points; compute the area of each triangle using the Shoelace formula.

Key Techniques

Array problems involve manipulating elements stored in a contiguous block of memory. Key techniques include two-pointer traversal, prefix sums, sliding windows, and in-place partitioning. In C#, arrays are zero-indexed and fixed in size — use List<T> when you need dynamic resizing.

Math

Math problems test number theory, combinatorics, and modular arithmetic. Common tools: GCD/LCM (Euclidean algorithm), prime sieve, modular inverse (Fermat's little theorem), digit manipulation, and bit tricks. Overflow is a key concern in C# — use long when products may exceed 2³¹.

Geometry

Geometry problems involve coordinates, lines, circles, and polygons. Key tools: cross product (orientation, area), dot product (angle), Graham scan (convex hull), and line intersection. Use long arithmetic to avoid floating-point errors when possible.

812.cs

// Approach: Brute-force all O(n³) triples of points; compute the area of each triangle using the Shoelace formula.
// Time: O(n³) Space: O(1)

public class Solution
{
    public double LargestTriangleArea(int[][] points)
    {
        double maxArea = 0;

        // Try all possible combinations of three points
        foreach (int[] point1 in points)
        {
            int x1 = point1[0];
            int y1 = point1[1];

            foreach (int[] point2 in points)
            {
                int x2 = point2[0];
                int y2 = point2[1];

                foreach (int[] point3 in points)
                {
                    int x3 = point3[0];
                    int y3 = point3[1];

                    // Calculate vectors from point1 to point2 and point1 to point3
                    int vectorX1 = x2 - x1;  // x component of vector from p1 to p2
                    int vectorY1 = y2 - y1;  // y component of vector from p1 to p2
                    int vectorX2 = x3 - x1;  // x component of vector from p1 to p3
                    int vectorY2 = y3 - y1;  // y component of vector from p1 to p3

                    // Calculate area using cross product formula
                    // Area = |cross product| / 2 = |v1 × v2| / 2
                    double currentArea = Math.Abs(vectorX1 * vectorY2 - vectorX2 * vectorY1) / 2.0;

                    // Update maximum area if current is larger
                    maxArea = Math.Max(maxArea, currentArea);
                }
            }
        }

        return maxArea;
    }
}

Was this solution helpful?