Minimum Score Triangulation of Polygon

Medium

Uber

4 views

Topics:

Dynamic Programming

You have a convex n-sided polygon where each vertex has an integer value. You are given an integer array values where values[i] is the value of the i^th vertex in clockwise order.

Polygon triangulation is a process where you divide a polygon into a set of triangles and the vertices of each triangle must also be vertices of the original polygon. Note that no other shapes other than triangles are allowed in the division. This process will result in n - 2 triangles.

You will triangulate the polygon. For each triangle, the weight of that triangle is the product of the values at its vertices. The total score of the triangulation is the sum of these weights over all n - 2 triangles.

Return the minimum possible score that you can achieve with some triangulation of the polygon.

Example 1:

Input: values = [1,2,3]

Output: 6

Explanation: The polygon is already triangulated, and the score of the only triangle is 6.

Example 2:

Input: values = [3,7,4,5]

Output: 144

Explanation: There are two triangulations, with possible scores: 3*7*5 + 4*5*7 = 245, or 3*4*5 + 3*4*7 = 144.
The minimum score is 144.

Example 3:

Input: values = [1,3,1,4,1,5]

Output: 13

Explanation: The minimum score triangulation is 1*1*3 + 1*1*4 + 1*1*5 + 1*1*1 = 13.

Constraints:

n == values.length
3 <= n <= 50
1 <= values[i] <= 100

Minimum Score Triangulation of Polygon

Medium

Uber

4 views

Topics:

Dynamic Programming

You have a convex n-sided polygon where each vertex has an integer value. You are given an integer array values where values[i] is the value of the i^th vertex in clockwise order.

Polygon triangulation is a process where you divide a polygon into a set of triangles and the vertices of each triangle must also be vertices of the original polygon. Note that no other shapes other than triangles are allowed in the division. This process will result in n - 2 triangles.

You will triangulate the polygon. For each triangle, the weight of that triangle is the product of the values at its vertices. The total score of the triangulation is the sum of these weights over all n - 2 triangles.

Return the minimum possible score that you can achieve with some triangulation of the polygon.

Example 1:

Input: values = [1,2,3]

Output: 6

Explanation: The polygon is already triangulated, and the score of the only triangle is 6.

Example 2:

Input: values = [3,7,4,5]

Output: 144

Explanation: There are two triangulations, with possible scores: 3*7*5 + 4*5*7 = 245, or 3*4*5 + 3*4*7 = 144.
The minimum score is 144.

Example 3:

Input: values = [1,3,1,4,1,5]

Output: 13

Explanation: The minimum score triangulation is 1*1*3 + 1*1*4 + 1*1*5 + 1*1*1 = 13.

Constraints:

n == values.length
3 <= n <= 50
1 <= values[i] <= 100

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for each vertex in the input array? Are they guaranteed to be positive integers?
What should I return if the input polygon has fewer than 3 vertices, making triangulation impossible?
Is the input list of vertices guaranteed to represent a convex polygon, or could it be concave?
Is the order of vertices in the input array clockwise or counterclockwise?
Are all the vertices guaranteed to be distinct (no duplicate vertex coordinates)?

Brute Force Solution

Approach

The problem is about dividing a polygon into triangles. The brute force approach tries every single way you can draw lines to form triangles inside the polygon and adds up some 'score' for each way.

Here's how the algorithm would work step-by-step:

Think about all the different lines you could possibly draw between the corners of the polygon to split it into triangles.
Pick one possible set of lines that divides the polygon completely into triangles (without any lines crossing each other).
Calculate the 'score' for that particular way of dividing it, based on some rules (usually multiplying the corners or something).
Now, try a different set of lines to divide the polygon into triangles. Calculate the 'score' for this new arrangement.
Keep doing this for every single possible way you can divide the polygon into triangles.
Once you've tried every single way, compare all the scores you calculated.
Find the lowest score among all the different triangle arrangements. That lowest score is your answer.

Code Implementation

def minimum_score_triangulation_brute_force(polygon):
    number_of_vertices = len(polygon)

    def calculate_score(triangle):
        return polygon[triangle[0]] * polygon[triangle[1]] * polygon[triangle[2]]

    def triangulate(current_polygon):
        if len(current_polygon) == 3:
            return calculate_score(current_polygon)

        minimum_triangulation_score = float('inf')

        # Iterate through all possible vertices to form triangles.
        for first_vertex_index in range(1, len(current_polygon) - 1):
            # Divide the polygon and recursively triangulate.

            first_triangle = (current_polygon[0], current_polygon[first_vertex_index], current_polygon[-1])
            first_triangle_score = calculate_score(first_triangle)

            left_polygon = tuple([current_polygon[index] for index in range(0, first_vertex_index + 1)])
            right_polygon = tuple([current_polygon[index] for index in range(first_vertex_index, len(current_polygon))])

            if len(left_polygon) > 2 and len(right_polygon) > 2:
                left_triangulation_score = triangulate(left_polygon)
                right_triangulation_score = triangulate(right_polygon)
                total_score = first_triangle_score + left_triangulation_score + right_triangulation_score
            elif len(left_polygon) > 2:
                left_triangulation_score = triangulate(left_polygon)
                total_score = first_triangle_score + left_triangulation_score
            elif len(right_polygon) > 2:
                right_triangulation_score = triangulate(right_polygon)
                total_score = first_triangle_score + right_triangulation_score
            else:
                total_score = first_triangle_score

            minimum_triangulation_score = min(minimum_triangulation_score, total_score)

        return minimum_triangulation_score

    # Creates an index tuple that represents the initial polygon
    initial_polygon_indices = tuple(range(number_of_vertices))
    return triangulate(initial_polygon_indices)

Big(O) Analysis

Time Complexity

O(n^3) – The problem involves considering all possible triangulations of the polygon. The number of possible triangulations grows exponentially with the number of vertices (n). We are effectively trying all possible combinations of diagonals to divide the polygon into triangles, and for each triangulation, we compute a score. The score calculation involves iterating through the triangles formed. Although the number of triangles is linearly proportional to 'n', exploring all possible triangulation configurations leads to a recursion depth of 'n'. Within the recursive calls, we have a loop that iterates up to 'n' times. Thus the time complexity is O(n^3) due to the number of ways to divide the polygon.

Space Complexity

O(N^2) – The brute force approach, as described, implicitly explores all possible triangulations, which is commonly implemented using recursion with memoization or dynamic programming. To store intermediate results and avoid redundant calculations, a memoization table or a DP table is typically used. This table will be of size N x N, where N is the number of vertices in the polygon, as it stores the minimum score for triangulating sub-polygons defined by vertices i to j. Therefore, the auxiliary space complexity is O(N^2).

Optimal Solution

Approach

The most efficient way to solve this polygon triangulation problem is to break it down into smaller, overlapping subproblems. We find the best way to triangulate each smaller piece of the polygon and combine those solutions to find the best solution for the whole thing. This avoids recomputing the same things over and over.

Here's how the algorithm would work step-by-step:

Imagine you're trying to cut the polygon into triangles, but you want to minimize the score for all the cuts.
Instead of trying all possible ways to cut the polygon, think about just one side of the polygon first. Consider all the different triangles you can make using that side as a base.
For each of those possible triangles, figure out the score of the triangle itself. Then, look at the two smaller polygons you've created by adding that triangle.
The key idea is that the best way to cut each of these smaller polygons *has already been calculated*. We stored those values when calculating earlier steps.
So, for each triangle, you add the score of the triangle to the *already calculated* scores for the two smaller polygons it creates. Find the smallest total score.
Store this smallest total score for future use. This is the best way to triangulate that specific part of the polygon.
Repeat this process for every side of the polygon, building up from smaller polygons to the whole thing. Each time you calculate a score, you're reusing previously calculated scores.
Eventually, you'll have calculated the best score for triangulating the entire polygon. This is the answer.

Code Implementation

def minimum_score_triangulation(polygon):
    number_of_points = len(polygon)
    # DP table to store min score for sub-polygons
    dp_table = [[0] * number_of_points for _ in range(number_of_points)]

    for polygon_size in range(2, number_of_points):
        for left_point in range(number_of_points - polygon_size):
            right_point = left_point + polygon_size
            dp_table[left_point][right_point] = float('inf')

            # Iterate through each possible vertex to form a triangle
            for current_point in range(left_point + 1, right_point):
                # The cost of the current triangle we are testing.
                cost_of_current_triangle = polygon[left_point] * polygon[current_point] * polygon[right_point]

                # Calculate the score with the current triangle
                total_score = dp_table[left_point][current_point] + dp_table[current_point][right_point] + cost_of_current_triangle
                dp_table[left_point][right_point] = min(dp_table[left_point][right_point], total_score)

    # The result is the minimum triangulation score for the entire polygon
    return dp_table[0][number_of_points - 1]

Big(O) Analysis

Time Complexity

O(n^3) – The algorithm uses dynamic programming to calculate the minimum triangulation score. It iterates through all possible polygon segments defined by indices i and j. For each segment (i, j), it considers all possible vertices k between i and j to form a triangle (i, k, j). This involves a triple nested loop structure: the outer loops iterating through all possible i and j, and the inner loop iterating through k. Thus, the algorithm has O(n*n*n) which is O(n^3) time complexity, where n is the number of vertices of the polygon. Specifically, the outer loops define subproblems of sizes ranging from 3 up to n, and the inner loop iterates over the number of vertices to consider as the third point of a triangle for that subproblem.

Space Complexity

O(N^2) – The algorithm stores the best way to triangulate each smaller part of the polygon using dynamic programming. This is implemented using a table (e.g., a 2D array or matrix) to store the minimum scores for triangulating sub-polygons defined by vertices i and j. The table's dimensions are proportional to the number of vertices, N, resulting in an N x N table. Therefore, the auxiliary space required is proportional to N squared, leading to a space complexity of O(N^2).

Edge Cases

Case	How to Handle
Null or empty input array	Return 0 as triangulation is impossible for an invalid polygon.
Array with fewer than 3 vertices	Return 0 as triangulation requires at least 3 vertices to form a polygon.
Array with exactly 3 vertices (a triangle)	Return 0 directly, as no further triangulation is needed and score is 0.
Large input size (n > 100)	DP solution should handle large inputs efficiently within time constraints; memoization avoids exponential recursion.
Integer overflow when calculating score products for large values	Use a data type that can store larger values (e.g., long) or implement checks to prevent overflow.
All vertices have the same value	The DP algorithm correctly calculates the minimum triangulation score even with identical vertex values.
Array is already sorted in increasing order.	The DP algorithm functions correctly regardless of the vertex order, by considering all possible triangulations.
Vertices form a degenerate polygon (self-intersecting)	The problem statement assumes a convex polygon; ensure constraints or pre-processing step before applying DP.