Maximum Height of a Triangle - Solution & Explanation
Problem Statement
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 <= 100
Approach Overview
Problem 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 1: Binary Search for Maximum Height
This approach involves binary searching the maximum possible height. First, understand that ith row needs exactly i balls. The maximum possible height we can achieve depends on the sum of the two sequences (using red and blue balls). We will perform binary search on the height. For a given middle point in the binary search, check if we can build a triangle of that height by considering alternating rows of red and blue balls. Adjust binary search bounds based on feasibility.
In this Python implementation, maximum_height uses binary search to determine the maximum height of the triangle that can be achieved. The helper function can_form_triangle calculates if it is feasible to form a triangle of a given height considering alternating color rows. Adjustments in binary search are made based on feasibility at the middle point.
Code
Python
Java
C++
JavaScript
Complexity
The time complexity is O(log N * H), where N is the maximum guessable height, and H is the height checked for each feasibility computation. The space complexity is O(1) since we are using a constant amount of space.
Approach 2: Greedy Approach
The greedy approach builds the triangle incrementally from the base. Starting from the first row, choose between using red or blue balls by alternating color for each subsequent row. This maximizes the triangle height by ensuring that balls are used efficiently.
The greedy approach in this Python solution iterates through rows and updates the count of red and blue balls. For each row, the solution alternates colors and reduces the count of balls accordingly. If a row cannot be constructed due to lack of balls, it returns the maximum feasible height.
Code
Python
Java
C++
JavaScript
Complexity
The time complexity is O(H), where H is the maximum possible height. The space complexity is O(1).
Approach 3: Simulation
We can enumerate the color of the first row, then simulate the construction of the triangle, calculating the maximum height.
The time complexity is O(\sqrt{n}), where n is the number of red and blue balls. The space complexity is O(1).
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Binary Search for Maximum Height | The time complexity is |
| Greedy Approach | The time complexity is |
| Simulation | — |
Detailed Complexity Analysis
| 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 |
Video Solution
3200 Maximum Height of a Triangle || How to 🤔 in Interview || Simulation ✅ • Ayush Rao • 2,078 views views
Watch 7 more video solutions →Frequently Asked Questions
Is Maximum Height of a Triangle easy or hard?
Maximum Height of a Triangle Python/Java solution
How to solve Maximum Height of a Triangle in O(log n)?
What is the best approach for Maximum Height of a Triangle?
Is Maximum Height of a Triangle asked at Google/Amazon/Meta?
What data structure is used in Maximum Height of a Triangle?
What is the time complexity of Maximum Height of a Triangle?
Ready to solve this problem?
Practice Maximum Height of a Triangle with our built-in code editor and test cases.
Practice on FleetCode