Largest Triangle Area - Practice Coding Problems

Largest Triangle Area - Problem

Given an array of points on the X-Y plane points where points[i] = [x_i, y_i], return the area of the largest triangle that can be formed by any three different points.

Answers within 10^-5 of the actual answer will be accepted.

Input & Output

Example 1 — Basic Triangle

$ Input: points = [[0,0],[0,1],[1,0],[2,1],[2,2]]

› Output: 2.0

💡 Note: The largest triangle is formed by points [0,0], [2,1], [2,2] with area = 2.0

Example 2 — Minimum Case

$ Input: points = [[1,0],[0,0],[0,1]]

› Output: 0.5

💡 Note: Only one triangle possible with points forming a right triangle, area = 0.5 * 1 * 1 = 0.5

Example 3 — Collinear Points

$ Input: points = [[0,0],[1,1],[2,2],[3,4]]

› Output: 1.5

💡 Note: Points [0,0], [1,1], [2,2] are collinear (area = 0), largest triangle uses [0,0], [2,2], [3,4]

Constraints

3 ≤ points.length ≤ 50
-50 ≤ x_i, y_i ≤ 50
All the given points are unique.

Visualization

Tap to expand

Understanding the Visualization

Input Points

Array of coordinate points [[0,0],[0,1],[1,0],[2,1],[2,2]]

Generate All Triangles

Test all possible combinations of 3 points

Find Maximum Area

Return the largest area found: 2.0

Key Takeaway

🎯 Key Insight: Use the cross product formula |x₁(y₂-y₃) + x₂(y₃-y₁) + x₃(y₁-y₂)| / 2 to calculate triangle area efficiently

Asked in

a Amazon 15 G Google 12

The key insight is to use the cross product formula to calculate triangle area efficiently. The best approach is the brute force method checking all C(n,3) combinations since n ≤ 50. Time: O(n³), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Optimized Brute Force	O(n³)	O(1)	Same approach but with optimized area calculation using integer arithmetic
Brute Force - Check All Combinations	O(n³)	O(1)	Try every possible combination of 3 points and calculate triangle area

Optimized Brute Force — Algorithm Steps

Step 1: Try all combinations of 3 points using triple nested loops
Step 2: Calculate area using integer cross product formula first
Step 3: Convert to floating point only for final comparison

Visualization

Tap to expand

Step-by-Step Walkthrough

Same Combinations

Still check all possible triangles

Integer Cross Product

Calculate cross product using integers first

Final Division

Convert to float only for the final area calculation

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

double solution(int points[][2], int n) {
    double maxArea = 0.0;
    
    // Try all combinations of 3 points
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            for (int k = j + 1; k < n; k++) {
                long long x1 = points[i][0], y1 = points[i][1];
                long long x2 = points[j][0], y2 = points[j][1];
                long long x3 = points[k][0], y3 = points[k][1];
                
                // Calculate cross product as long long first
                long long crossProduct = x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2);
                if (crossProduct < 0) crossProduct = -crossProduct;
                double area = crossProduct / 2.0;
                
                if (area > maxArea) maxArea = area;
            }
        }
    }
    
    return maxArea;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Simple parsing for [[x1,y1],[x2,y2],...]
    int points[50][2];
    int n = 0;
    char *ptr = line + 1;
    
    while (*ptr && *ptr != ']') {
        if (*ptr == '[') {
            ptr++;
            points[n][0] = atoi(ptr);
            while (*ptr && *ptr != ',') ptr++;
            ptr++;
            points[n][1] = atoi(ptr);
            while (*ptr && *ptr != ']') ptr++;
            ptr++;
            n++;
        }
        ptr++;
    }
    
    double result = solution(points, n);
    printf("%f\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

Still need to check all combinations of 3 points

⚠ Quadratic Growth

Space Complexity

O(1)

Only using constant extra space for variables

✓ Linear Space

28.5K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler