You are given two integers red and blue representing the count of red and blue colored balls. You have to arrange these balls to form a triangle such that the 1st row will have 1 ball, the 2nd row will have 2 balls, the 3rd row will have 3 balls, and so on.
All the balls in a particular row should be the same color, and adjacent rows should have different colors.
Return the maximum height of the triangle that can be achieved.
Example 1:
Input: red = 2, blue = 4
Output: 3
Explanation:
The only possible arrangement is shown above.
Example 2:
Input: red = 2, blue = 1
Output: 2
Explanation:
The only possible arrangement is shown above.
Example 3:
Input: red = 1, blue = 1
Output: 1
Example 4:
Input: red = 10, blue = 1
Output: 2
Explanation:
The only possible arrangement is shown above.
Constraints:
1 <= red, blue <= 100In #3200 Maximum Height of a Triangle, you are given counts of two different colored blocks and must build the tallest possible triangle. The triangle has i blocks in the i-th row, and adjacent rows must use different colors. The key idea is to determine how many rows can be formed while respecting both the increasing block requirement and the color alternation constraint.
A practical strategy is to enumerate the height of the triangle while tracking how many blocks of each color are required. Since rows alternate colors, you should evaluate two cases: starting with the first color or starting with the second color. For a given height h, odd-indexed rows consume one color and even-indexed rows consume the other.
By incrementally building rows (1, 2, 3, ... blocks) and subtracting from the available counts, you can stop when either color runs out. The maximum valid height across both starting scenarios is the answer. This greedy enumeration works efficiently because the number of rows grows roughly with the square root of the total blocks.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Greedy Enumeration of Triangle Height | O(h) where h is the maximum possible height (≈ √n) | O(1) |
CrioDo
Use these hints if you're stuck. Try solving on your own first.
Count the max height using both possibilities. That is, red ball as top and blue ball as top.
For counting the max height, use a simple for loop and remove the number of balls required at this level.
Watch expert explanations and walkthroughs
Jot down your thoughts, approach, and key learnings
While this exact problem may not always appear, similar greedy and enumeration-based problems are common in technical interviews. Understanding how to simulate constraints and test multiple starting conditions is a valuable interview skill.
No complex data structure is required for this problem. Simple integer counters for each color and a loop to simulate row construction are sufficient. The logic mainly relies on arithmetic and enumeration.
The optimal approach is to greedily simulate building the triangle row by row while alternating colors. You evaluate both possible starting colors and keep adding rows until one color runs out of blocks. The maximum height achieved across both cases is the result.
Because the first row determines which color is used on odd and even rows. Starting with a different color changes the distribution of blocks required for each color. Checking both ensures we do not miss the configuration that yields a taller triangle.