#3200

Easy

LeetCode Problem Workspace

Maximum Height of a Triangle

Find the maximum height of a triangle that can be formed using red and blue balls under given constraints.

Problem Statement

You are given two integers, red and blue, which represent the number of red and blue balls, respectively. The goal is to arrange these balls into a triangle, with the first row containing 1 ball, the second row containing 2 balls, the third row containing 3 balls, and so on, following a sequential pattern.

Each row must be filled with balls of the same color, and consecutive rows must alternate in color. Return the maximum height of the triangle that can be formed with the given constraints.

Examples

Example 1

Input: red = 2, blue = 4

Output: 3

The only possible arrangement is shown above.

Example 2

Input: red = 2, blue = 1

Output: 2

The only possible arrangement is shown above.

Example 3

Input: red = 1, blue = 1

Output: 1

Example details omitted.

Constraints

1 <= red, blue <= 100

Solution Approach

Simulate the Triangle Formation

Iterate through possible row formations starting with red on the top and then switching the colors. For each configuration, simulate the triangle formation and track the maximum height possible given the constraints.

Count Maximum Height Using Red and Blue

Check both possibilities for maximum triangle height: red as the top row and blue as the top row. Compare the heights for both cases and return the maximum.

Greedy Enumeration Approach

Use a greedy approach to maximize the height by alternating colors. Enumerate all possibilities where rows can be red or blue and calculate the maximum height based on ball count limitations.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time and space complexity will depend on the implementation of the greedy enumeration approach, which is typically O(N) for simulating each possible configuration, where N is the maximum number of rows that can fit within the given red and blue balls.

What Interviewers Usually Probe

Candidate demonstrates understanding of array plus enumeration.
Candidate should be able to correctly switch between color configurations.
Check if candidate understands the importance of maximizing row formation without violating color constraints.

Common Pitfalls or Variants

Common pitfalls

Misunderstanding the row constraints, especially with alternating colors.
Failing to account for both color possibilities (red or blue on top).
Incorrectly calculating the number of rows that can be formed given the available red and blue balls.

Follow-up variants

What if the number of balls is drastically different between red and blue?
How would the problem change if the number of rows allowed was capped?
What if additional color constraints were introduced, such as using multiple colors?

FAQ

What is the pattern used in the Maximum Height of a Triangle problem?

The problem follows an array plus enumeration pattern, where different configurations of alternating row colors need to be evaluated to maximize the triangle's height.

What is the maximum height of the triangle if the red balls are much fewer than the blue balls?

In this case, the maximum height will depend on the number of rows that can be filled using the available red balls, while adhering to the alternating color constraint.

How does the alternating color requirement affect the triangle's height?

The alternating color requirement means that the sequence of rows must alternate between red and blue balls. This constraint limits the number of rows that can be formed with the given red and blue balls.

Can I use any color combination for the rows in the Maximum Height of a Triangle problem?

No, you must alternate the color of adjacent rows, which restricts your choices to two configurations: red on top or blue on top.

What is the expected time complexity of solving the Maximum Height of a Triangle problem?

The time complexity depends on the approach you use to simulate the ball arrangement, but a greedy enumeration approach typically has a time complexity of O(N), where N is the number of rows that can be formed.

terminal

Solution

Solution 1: Simulation

We can enumerate the color of the first row, then simulate the construction of the triangle, calculating the maximum height.

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def maxHeightOfTriangle(self, red: int, blue: int) -> int:
        ans = 0
        for k in range(2):
            c = [red, blue]
            i, j = 1, k
            while i <= c[j]:
                c[j] -= i
                j ^= 1
                ans = max(ans, i)
                i += 1
        return ans

Continue Practicing

#3197 find the minimum area to cover all ones ii #3256 maximum value sum by placing three rooks i #3257 maximum value sum by placing three rooks ii