LeetCode Problem 3200

Difficulty: 🟢 Easy
Topics: Array, Enumeration

Solution

LeetCode 3200 - Maximum Height of a Triangle

Problem Understanding

The problem gives us two integers, red and blue, representing the number of red and blue balls available. We want to build a triangle where:

• Row 1 contains exactly 1 ball
• Row 2 contains exactly 2 balls
• Row 3 contains exactly 3 balls
• And so on

There are two additional restrictions:

1. Every ball in the same row must have the same color.
2. Adjacent rows must use different colors.

This means the colors must alternate between rows. For example:

• Red, Blue, Red, Blue, ...
• Or Blue, Red, Blue, Red, ...

The goal is to compute the maximum possible height of such a triangle.

The constraints are very small:

• 1 <= red, blue <= 100

This tells us that even a brute-force simulation would be acceptable. We do not need advanced optimization techniques because the maximum possible height is small.

The important detail is that we must consider both possible starting colors:

• Start with red on row 1
• Start with blue on row 1

The larger valid height from these two configurations is the answer.

Several edge cases are important:

• One color may be much larger than the other, such as red = 10, blue = 1
• Both colors may be very small, such as red = 1, blue = 1
• The limiting factor is usually whichever color runs out first
• Alternating rows means we cannot freely distribute balls between colors

A naive implementation that only tries one starting color can easily fail.

Approaches

Brute Force Approach

The brute-force solution tries to build the triangle row by row.

We simulate the process twice:

1. Assume the first row uses red
2. Assume the first row uses blue

For each simulation:

• Start at row size 1
• Deduct balls from the appropriate color
• Alternate colors each row
• Stop once we cannot fill the next row

The maximum height achieved across both simulations is the answer.

This approach is correct because every valid triangle must follow one of the two possible alternating color patterns.

Even though this is called brute force, the constraints are tiny, so the solution is completely practical.

Key Insight for the Optimal Approach

The important observation is that there are only two possible coloring patterns:

• Red, Blue, Red, Blue, ...
• Blue, Red, Blue, Red, ...

Once the starting color is fixed, the rest of the triangle is fully determined.

This means we never need to search through combinations or backtracking states. We only need to simulate the construction process for the two valid alternating patterns.

Because the maximum height is small, a direct greedy simulation is both simple and optimal.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(h)	O(1)	Simulates row construction sequentially
Optimal	O(h)	O(1)	Same simulation, but based on the observation that only two patterns exist

Here, h is the maximum achievable height, which is at most around 14 because 1 + 2 + ... + 14 = 105.

Algorithm Walkthrough

Optimal Algorithm

1. Create a helper function that simulates triangle construction for a chosen starting color.
2. Initialize:

• current_row = 1
• Remaining counts of red and blue balls

3. Determine which color the current row should use.

• If starting with red:

• Odd rows use red

• Even rows use blue

• If starting with blue:

• Odd rows use blue

• Even rows use red

4. Check whether the required number of balls exists for the current row.

• If not enough balls remain, stop immediately.
• Otherwise, subtract the balls and continue.

5. Increment the row number and repeat the process.
6. The height achieved is current_row - 1, because the loop stops after failing to build the next row.
7. Run the simulation twice:

• Once starting with red
• Once starting with blue

8. Return the maximum of the two heights.

Why it works

The alternating-color restriction completely determines the color of every row once the starting color is chosen. Therefore, every valid triangle must belong to exactly one of the two simulated patterns.

The algorithm greedily builds rows in order from smallest to largest. Since row sizes strictly increase, skipping a row is impossible. If we cannot build row k, then no taller triangle can exist for that starting pattern.

Therefore, the simulation always produces the maximum valid height.

Python Solution

class Solution:
    def maxHeightOfTriangle(self, red: int, blue: int) -> int:
        def build_height(start_with_red: bool) -> int:
            remaining_red = red
            remaining_blue = blue
            row = 1

            while True:
                use_red = (row % 2 == 1) == start_with_red

                if use_red:
                    if remaining_red < row:
                        break
                    remaining_red -= row
                else:
                    if remaining_blue < row:
                        break
                    remaining_blue -= row

                row += 1

            return row - 1

        return max(
            build_height(True),
            build_height(False)
        )

The implementation uses a nested helper function named build_height. This function simulates constructing the triangle while assuming a fixed starting color.

The variables remaining_red and remaining_blue track how many balls are still available. The variable row represents the size of the current row being constructed.

The expression:

use_red = (row % 2 == 1) == start_with_red

determines whether the current row should use red balls. If the current row cannot be completed because there are not enough balls of the required color, the loop stops immediately.

Finally, we run the simulation twice, once for each possible starting color, and return the larger result.

Go Solution

func maxHeightOfTriangle(red int, blue int) int {
	buildHeight := func(startWithRed bool) int {
		remainingRed := red
		remainingBlue := blue
		row := 1

		for {
			useRed := (row%2 == 1) == startWithRed

			if useRed {
				if remainingRed < row {
					break
				}
				remainingRed -= row
			} else {
				if remainingBlue < row {
					break
				}
				remainingBlue -= row
			}

			row++
		}

		return row - 1
	}

	height1 := buildHeight(true)
	height2 := buildHeight(false)

	if height1 > height2 {
		return height1
	}

	return height2
}

The Go implementation follows the exact same logic as the Python version.

One small difference is that Go does not support nested named functions in the same way as Python, so we use an anonymous function assigned to buildHeight.

Integer overflow is not a concern because the constraints are extremely small.

Worked Examples

Example 1

Input:

red = 2, blue = 4

Start with red

Row	Color	Balls Needed	Remaining Red	Remaining Blue	Result
1	Red	1	1	4	Success
2	Blue	2	1	2	Success
3	Red	3	1	2	Fail

Height achieved = 2

Start with blue

Row	Color	Balls Needed	Remaining Red	Remaining Blue	Result
1	Blue	1	2	3	Success
2	Red	2	0	3	Success
3	Blue	3	0	0	Success
4	Red	4	0	0	Fail

Height achieved = 3

Answer:

3

Example 2

Input:

red = 2, blue = 1

Start with red

Row	Color	Balls Needed	Remaining Red	Remaining Blue	Result
1	Red	1	1	1	Success
2	Blue	2	1	1	Fail

Height achieved = 1

Start with blue

Row	Color	Balls Needed	Remaining Red	Remaining Blue	Result
1	Blue	1	2	0	Success
2	Red	2	0	0	Success
3	Blue	3	0	0	Fail

Height achieved = 2

Answer:

2

Example 3

Input:

red = 1, blue = 1

Start with red

Row	Color	Balls Needed	Remaining Red	Remaining Blue	Result
1	Red	1	0	1	Success
2	Blue	2	0	1	Fail

Height achieved = 1

Start with blue

The same result occurs.

Answer:

1

Example 4

Input:

red = 10, blue = 1

Start with red

Row	Color	Balls Needed	Remaining Red	Remaining Blue	Result
1	Red	1	9	1	Success
2	Blue	2	9	1	Fail

Height achieved = 1

Start with blue

Row	Color	Balls Needed	Remaining Red	Remaining Blue	Result
1	Blue	1	10	0	Success
2	Red	2	8	0	Success
3	Blue	3	8	0	Fail

Height achieved = 2

Answer:

2

Complexity Analysis

Measure	Complexity	Explanation
Time	O(h)	We simulate each row once
Space	O(1)	Only a few variables are used

The variable h represents the maximum achievable height. Since row sizes grow as 1 + 2 + 3 + ... + h, the height is naturally small under the problem constraints.

Even in the worst case, the loop executes only a small number of times.

Test Cases

solution = Solution()

assert solution.maxHeightOfTriangle(2, 4) == 3  # example 1
assert solution.maxHeightOfTriangle(2, 1) == 2  # example 2
assert solution.maxHeightOfTriangle(1, 1) == 1  # example 3
assert solution.maxHeightOfTriangle(10, 1) == 2  # example 4

assert solution.maxHeightOfTriangle(1, 2) == 2  # opposite imbalance
assert solution.maxHeightOfTriangle(3, 3) == 2  # balanced counts
assert solution.maxHeightOfTriangle(4, 6) == 3  # enough for 3 rows
assert solution.maxHeightOfTriangle(6, 6) == 4  # balanced larger case
assert solution.maxHeightOfTriangle(100, 100) == 19  # near upper constraint
assert solution.maxHeightOfTriangle(100, 1) == 2  # one color dominates
assert solution.maxHeightOfTriangle(1, 100) == 2  # reverse dominance
assert solution.maxHeightOfTriangle(7, 14) == 5  # alternating usage stress
assert solution.maxHeightOfTriangle(15, 15) == 7  # larger balanced case

Test	Why
(2, 4)	Verifies the first official example
(2, 1)	Verifies the second official example
(1, 1)	Smallest balanced input
(10, 1)	One color heavily dominates
(1, 2)	Reverse imbalance case
(3, 3)	Simple balanced configuration
(4, 6)	Tests medium-sized valid triangle
(6, 6)	Balanced larger case
(100, 100)	Maximum constraint values
(100, 1)	Extreme imbalance
(1, 100)	Reverse extreme imbalance
(7, 14)	Alternation-heavy scenario
(15, 15)	Larger symmetric case

Edge Cases

Extremely Unbalanced Colors

A common source of bugs is assuming that having many balls of one color automatically allows a tall triangle. For example:

red = 100, blue = 1

Even though there are many red balls, the alternating rule forces blue rows to appear. Once blue runs out, construction must stop. The implementation handles this naturally because each row explicitly checks the required color before continuing.

Very Small Inputs

Inputs like:

red = 1, blue = 1

can expose off-by-one errors. The algorithm correctly returns height 1 because row 2 would require two balls of the opposite color, which do not exist. Returning row - 1 after the loop ensures correctness.

Choosing the Wrong Starting Color

Some inputs only achieve the optimal answer with a specific starting color. For example:

red = 2, blue = 4

Starting with red gives height 2, but starting with blue gives height 3. A solution that only tries one configuration would fail. The implementation avoids this issue by simulating both possible starting colors and taking the maximum.