Maximum Height of a Triangle — Easy Problem & Solution

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…

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

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, …, taking row balls from whichever colour that row uses.
Stop when the required colour has fewer than row balls 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))

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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue