Watch 10 video solutions for Maximum Height of a Triangle, a easy level problem involving Array, Enumeration. This walkthrough by Ayush Rao has 2,058 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 100Problem Overview: You are given counts of red and blue blocks. Build a triangle where row i contains exactly i blocks. Each row must use a single color and adjacent rows must alternate colors. The task is to compute the maximum possible height you can build without exceeding the available blocks.
Approach 1: Greedy Row Simulation (O(h) time, O(1) space)
Simulate building the triangle row by row while alternating colors. Start with either red or blue and try both possibilities. For row i, check whether the required number of blocks exists for the current color. If enough blocks remain, subtract i from that color and move to the next row while switching colors. Stop once a row cannot be filled. The height reached before failure is the achievable triangle height for that starting color. Run the simulation twice (start red, start blue) and take the maximum. Since the height grows roughly with sqrt(red + blue), the loop stays small. This direct enumeration pattern commonly appears in enumeration style problems.
Approach 2: Binary Search for Maximum Height (O(log n) time, O(1) space)
Instead of simulating every row, search for the largest height h that satisfies the block constraints. For a candidate height, compute how many blocks each color needs depending on the starting color. If red is used on odd rows, the required red blocks equal the sum of odd row sizes 1 + 3 + 5 + ..., which equals (ceil(h/2))^2. Blue blocks cover the even rows 2 + 4 + ..., which equals k(k+1) where k = floor(h/2). Swap the formulas when starting with blue. If both color counts fit within the available blocks, the height is feasible. Binary search the range [0, red + blue] (effectively bounded by sqrt(n)) to find the maximum valid height. This approach demonstrates classic binary search on the answer.
Recommended for interviews: The greedy simulation is usually the first solution interviewers expect because it directly models the process and is easy to reason about. Showing the binary search optimization proves you recognize monotonic feasibility and can convert the problem into a search space problem. Both approaches rely on simple arithmetic and sequential checks, often categorized under array-style reasoning and enumeration patterns.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Row Simulation | O(h) ~ O(sqrt(n)) | O(1) | Best for quick implementation and clear reasoning in interviews |
| Binary Search on Height | O(log n) | O(1) | When recognizing monotonic feasibility and optimizing enumeration |