How do you solve Maximum Height of a Triangle on LeetCode?

Maximum Height of a Triangle (LeetCode #3200) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(1) space complexity. Key insight: The arrangement must alternate colors, which limits how many rows can be formed.

What is the brute force solution for Maximum Height of a Triangle?

The brute force approach for Maximum Height of a Triangle is Brute Force, with O(n²) time complexity and O(1) space complexity. We can try to build the triangle row by row, alternating colors. For each row, we check if we have enough balls of the required color. If we run out of balls, we stop and return the height achieved. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Maximum Height of a Triangle?

Maximum Height of a Triangle uses the following concepts: Array, Enumeration. The recommended patterns to study are: Greedy, Enumeration.

What are the interview tips for Maximum Height of a Triangle?

Always clarify the problem statement and constraints before jumping to code. Think about edge cases, such as when one color has significantly more balls than the other. Practice explaining your thought process as you code.

What are common mistakes when solving Maximum Height of a Triangle?

Forgetting to alternate colors correctly. Not considering both configurations (red on top and blue on top).

#3200

Maximum Height of a Triangle

Easy

ArrayEnumerationGreedyEnumeration

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(1)

💡

Intuition

Time O(n)Space O(1)

Instead of simulating each row, we can calculate the maximum height directly by determining how many complete rows we can form with the available balls. This is done by checking both configurations (red on top and blue on top) and taking the maximum.

⚙️

Algorithm

3 steps

1Step 1: Define a function to calculate the maximum height for a given top color.
2Step 2: Use a loop to calculate how many rows can be formed until we run out of balls.
3Step 3: Compare the heights obtained from both configurations and return the maximum.

solution.py11 lines

1def maxHeight(red, blue):
2    def calculate_height(r, b):
3        height = 0
4        while r >= height + 1 or b >= height + 1:
5            height += 1
6            if height % 2 == 1:
7                r -= height
8            else:
9                b -= height
10        return height
11    return max(calculate_height(red, blue), calculate_height(blue, red))

ℹ

Complexity note: The time complexity is O(n) because we are iterating through the number of rows we can build until we run out of balls, which is linear with respect to the maximum height.

1The arrangement must alternate colors, which limits how many rows can be formed.
2The maximum height is determined by the color with the fewer balls when alternating.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.