Maximum Height of a Triangle

Easy
841.

Maximum Height of a Triangle

Maximum Height of a Triangle is an easy coding problem on arrays, greedy and simulation, asked in Amazon, Adobe and Accenture interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} red
 * @param {number} blue
 * @return {number}
 */
var maxHeightOfTriangle = function(red, blue) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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

  1. Hint 1

    The colour of row 1 fixes every other row's colour, so there are only two arrangements to try.

  2. Hint 2

    Simulate each one: rows 1, 3, 5, … take the first colour and rows 2, 4, 6, … the other.

  3. 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

  1. For a starting colour, walk row = 1, 2, 3, …, taking row balls from whichever colour that row uses.
  2. Stop when the required colour has fewer than row balls left; the height is the number of completed rows.
  3. 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