Maximum Height of a Triangle solution and explanation
7 more videos on this problem
3200 Maximum Height of a Triangle || How to 🤔 in Interview || Simulation ✅Ayush Rao · 4:54 · 2K views
3200. Maximum Height of a Triangle (Leetcode Easy)Programming Live with Larry · 9:20 · 1K views
Leetcode contest 404 | Maximum Height of a Triangle |Leetcode 3200 IN JAVA | MAANG Interview | DSACode Thoughts · 6:34 · 423 views
leetcode 3200 : max height of a triangle : python solutionleetcode blind 75 · 6:13 · 311 views
3200. Maximum Height of a Triangle #leetcode #googleinterview #dsa #dsalgo #programming #dsa #codingCodeVia · 3:38 · 209 views
3200. Maximum Height of a Triangle (leetcode easy)Coder on A Farm · 4:08 · 175 views
Lesson 628/№3200. Maximum Height of a Triangle / LeetcodeYersham · 18:38 · 109 views
LeetCode 3200: Maximum Height of a Triangle | C# Solution | Geometry & MathCode Scribbler · 5:31 · 82 views
The problem
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.
def maximum_height(red, blue):
def can_form_triangle(height):
total_balls_needed = (height * (height + 1)) // 2
red_needed = sum(range(1, height + 1, 2))
blue_needed = total_balls_needed - red_needed
return (red >= red_needed and blue >= blue_needed) or (red >= blue_needed and blue >= red_needed)
low, high = 0, 200 # 200 is an arbitrarily large number
while low < high:
mid = (low + high + 1) // 2
if can_form_triangle(mid):
low = mid
else:
high = mid - 1
return lowpublic class Solution {
public int maximumHeight(int red, int blue) {
int low = 0, high = 200;
while (low < high) {
int mid = (low + high + 1) / 2;
if (canFormTriangle(mid, red, blue)) {
low = mid;
} else {
high = mid - 1;
}
}
return low;
}
private boolean canFormTriangle(int height, int red, int blue) {
int totalBallsNeeded = (height * (height + 1)) / 2;
int redNeeded = (height + 1) / 2 * height / 2; // sum of odd indices
int blueNeeded = totalBallsNeeded - redNeeded;
return (red >= redNeeded && blue >= blueNeeded) || (red >= blueNeeded && blue >= redNeeded);
}
}#include <iostream>
bool canFormTriangle(int height, int red, int blue) {
int totalBallsNeeded = (height * (height + 1)) / 2;
int redNeeded = (height + 1) / 2 * height / 2;
int blueNeeded = totalBallsNeeded - redNeeded;
return (red >= redNeeded && blue >= blueNeeded) || (red >= blueNeeded && blue >= redNeeded);
}
int maximumHeight(int red, int blue) {
int low = 0, high = 200;
while (low < high) {
int mid = (low + high + 1) / 2;
if (canFormTriangle(mid, red, blue)) {
low = mid;
} else {
high = mid - 1;
}
}
return low;
}
int main() {
int red = 10, blue = 1;
std::cout << "Maximum Height of a Triangle: " << maximumHeight(red, blue) << std::endl;
return 0;
}function maximumHeight(red, blue) {
const canFormTriangle = (height) => {
const totalBallsNeeded = (height * (height + 1)) / 2;
const redNeeded = Math.floor((height + 1) / 2) * Math.floor(height / 2);
const blueNeeded = totalBallsNeeded - redNeeded;
return (red >= redNeeded && blue >= blueNeeded) || (red >= blueNeeded && blue >= redNeeded);
};
let low = 0, high = 200;
while (low < high) {
const mid = Math.floor((low + high + 1) / 2);
if (canFormTriangle(mid)) {
low = mid;
} else {
high = mid - 1;
}
}
return low;
}
console.log(maximumHeight(10, 1)); // Outputs: 2In 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.
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.
def maximum_height(red, blue):
height, total_balls = 0, 0
while True:
height += 1
if height % 2 != 0: # Odd row, try using red if possible
if red >= height:
red -= height
else:
return height - 1
else: # Even row, try using blue
if blue >= height:
blue -= height
else:
return height - 1
# Example Usage
print(maximum_height(10, 1)) # Output: 2public class Solution {
public int maximumHeight(int red, int blue) {
int height = 0;
while (true) {
height++;
if (height % 2 != 0) { // Odd row
if (red >= height) {
red -= height;
} else {
return height - 1;
}
} else { // Even row
if (blue >= height) {
blue -= height;
} else {
return height - 1;
}
}
}
}
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println(sol.maximumHeight(10, 1)); // Output: 2
}
}#include <iostream>
int maximumHeight(int red, int blue) {
int height = 0;
while (true) {
height++;
if (height % 2 != 0) { // Odd row
if (red >= height) {
red -= height;
} else {
return height - 1;
}
} else { // Even row
if (blue >= height) {
blue -= height;
} else {
return height - 1;
}
}
}
}
int main() {
int red = 10, blue = 1;
std::cout << "Maximum Height: " << maximumHeight(red, blue) << std::endl; // Output: 2
return 0;
}function maximumHeight(red, blue) {
let height = 0;
while (true) {
height++;
if (height % 2 !== 0) { // Odd row
if (red >= height) {
red -= height;
} else {
return height - 1;
}
} else { // Even row
if (blue >= height) {
blue -= height;
} else {
return height - 1;
}
}
}
}
console.log(maximumHeight(10, 1)); // Output: 2The 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.
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).
function maxHeightOfTriangle(red: number, blue: number): number {
let ans = 0;
for (let k = 0; k < 2; ++k) {
const c: [number, number] = [red, blue];
for (let i = 1, j = k; i <= c[j]; ++i, j ^= 1) {
c[j] -= i;
ans = Math.max(ans, i);
}
}
return ans;
}func maxHeightOfTriangle(red int, blue int) (ans int) {
for k := 0; k < 2; k++ {
c := [2]int{red, blue}
for i, j := 1, k; i <= c[j]; i, j = i+1, j^1 {
c[j] -= i
ans = max(ans, i)
}
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Binary Search for Maximum Height | The time complexity is |
| Greedy Approach | The time complexity is |
| Simulation | – |
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 |
Frequently asked questions
Is Maximum Height of a Triangle easy or hard?
Maximum Height of a Triangle is classified as an Easy problem. The logic involves simple greedy simulation and arithmetic series formulas. The challenge mainly lies in recognizing the alternating color pattern and computing row requirements correctly.
Maximum Height of a Triangle Python/Java solution
Python, Java, C++, and JavaScript implementations typically simulate rows greedily or apply binary search on the height. Both versions only track remaining red and blue counts and compute required blocks per row, keeping the space complexity O(1).
How to solve Maximum Height of a Triangle in O(log n)?
Use binary search on the possible triangle height. For each candidate height h, compute the number of blocks needed for odd and even rows using arithmetic series formulas. Check both starting configurations (red first or blue first). If the required blocks fit within the available counts, increase the search range; otherwise decrease it.
What is the best approach for Maximum Height of a Triangle?
The greedy row simulation is the most intuitive approach. Simulate building rows one by one while alternating colors and subtracting the required blocks for each row. Try both starting colors and take the maximum height. This runs in about O(sqrt(n)) time because the triangle height grows roughly with the square root of the total blocks.
Is Maximum Height of a Triangle asked at Google/Amazon/Meta?
The problem pattern appears in interviews at companies like Amazon and Google under greedy simulation or binary-search-on-answer categories. Interviewers often expect candidates to first simulate the process and then recognize the mathematical pattern for optimization.
What data structure is used in Maximum Height of a Triangle?
No complex data structures are required. The solution relies on simple arithmetic calculations and iterative checks. The core idea is enumeration of rows or binary search on the answer combined with constant-time math formulas.
What is the time complexity of Maximum Height of a Triangle?
The greedy simulation runs in O(h) time where h is the triangle height, which is approximately O(sqrt(red + blue)). A binary search optimization reduces the complexity to O(log n) by searching for the largest feasible height and checking color requirements using closed-form formulas.