Maximum Height of a Triangle — Problem & Solution
Maximum Height of a Triangle solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Maximum Height of a Triangle is an easy coding problem on arrays, greedy and simulation, asked in Amazon, Adobe and Accenture interviews.
- Difficulty: Easy
- Topics: Arrays, Greedy, Simulation, Enumeration
- Asked at: Amazon, Adobe, Accenture
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You have red red balls and blue blue balls. Arrange some of them into a triangle where row i (1-indexed) holds exactly i balls, every ball in a row shares a colour, and adjacent rows have different colours.
Return the maximum height of such a triangle.
Example 1
Input: red = 2, blue = 4
Output: 3
Explanation: Rows of 1 red, 2 blue and 3 — starting blue gives blue, red, blue using 4 blue and 2 red.
Example 2
Input: red = 2, blue = 1
Output: 2
Explanation: 1 blue then 2 red.
Example 3
Input: red = 10, blue = 1
Output: 2
Explanation: Only one blue ball, so the triangle stops after two rows.
Constraints
1 <= red, blue <= 100
Hints for Maximum Height of a Triangle
Hint 1
The colour of row 1 fixes every other row's colour, so there are only two arrangements to try.
Hint 2
Simulate each one: rows 1, 3, 5, … take the first colour and rows 2, 4, 6, … the other.
Hint 3
Stop as soon as a row cannot be filled, and take the better of the two heights.
How to solve Maximum Height of a Triangle
Adjacent rows alternate, so once row 1's colour is chosen the whole triangle's colouring is determined. That leaves exactly two candidates, each of which is a short simulation.
Approach
- For a starting colour, walk
row = 1, 2, 3, …, takingrowballs from whichever colour that row uses. - Stop when the required colour has fewer than
rowballs left; the height is the number of completed rows. - Return the maximum over the two starting colours.
Why it works
There is nothing to optimise inside a run — each row's size and colour are forced — so the only decision is which colour goes first, and trying both is exhaustive. The simulation terminates quickly because the triangle's total grows quadratically while the supply is bounded by 200.
Complexity
- Time —
O(sqrt(red + blue)) - Space —
O(1)
Pitfalls
- Trying only one starting colour misses cases like
red = 2, blue = 4. - A row must be filled completely; a partial row does not count.
- The height is the count of completed rows, not the index of the failing one.
Reference solution
Python
def maxHeightOfTriangle(red: int, blue: int) -> int:
def run(first: int, second: int) -> int:
h, a, b = 0, first, second
row = 1
while True:
if row % 2 == 1:
if a < row:
break
a -= row
else:
if b < row:
break
b -= row
h += 1
row += 1
return h
return max(run(red, blue), run(blue, red))Java
private static int runTriangle(int first, int second) {
int h = 0, a = first, b = second;
for (int row = 1; ; row++) {
if (row % 2 == 1) {
if (a < row) break;
a -= row;
} else {
if (b < row) break;
b -= row;
}
h++;
}
return h;
}
public static int maxHeightOfTriangle(int red, int blue) {
return Math.max(runTriangle(red, blue), runTriangle(blue, red));
}C++
static int runTriangle(int first, int second) {
int h = 0, a = first, b = second;
for (int row = 1; ; row++) {
if (row % 2 == 1) {
if (a < row) break;
a -= row;
} else {
if (b < row) break;
b -= row;
}
h++;
}
return h;
}
int maxHeightOfTriangle(int red, int blue) {
return max(runTriangle(red, blue), runTriangle(blue, red));
}JavaScript
var maxHeightOfTriangle = function(red, blue) {
var run = function(first, second) {
var h = 0, a = first, b = second;
for (var row = 1; ; row++) {
if (row % 2 === 1) {
if (a < row) break;
a -= row;
} else {
if (b < row) break;
b -= row;
}
h++;
}
return h;
};
return Math.max(run(red, blue), run(blue, red));
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Greedy Algorithms