Maximum Height of a Triangle

Maximum Height of a Triangle

What is this problem about?

The Maximum Height of a Triangle coding problem gives you two colors of balls (say red and blue) with counts red and blue. You want to build the tallest possible triangle where each row must be filled with balls of a single color, alternating colors between rows, and row k requires exactly k balls. Maximize the number of rows (height) you can form.

Why is this asked in interviews?

Salesforce includes this problem to test greedy thinking and simulation under constraints. While the problem sounds simple, it requires careful enumeration of both starting-color possibilities and correct tracking of ball counts. It is a good warm-up problem for greedy interviews and tests whether candidates can handle state simulation without overcomplicating it.

Algorithmic pattern used

The solution uses greedy enumeration. Try both starting configurations: start with color A on row 1, or start with color B on row 1. For each configuration, simulate building rows greedily: row k uses k balls of the current color. If you run out of the current color's balls, stop. Track the maximum height across both configurations. Each simulation is O(sqrt(n)) since the total balls used up to row h is h*(h+1)/2.

Example explanation

Red = 4, Blue = 6.

• Start red: Row 1 (1 red, rem=3), Row 2 (2 blue, rem=4), Row 3 (3 red, rem=0), Row 4 (4 blue, rem=0). Height = 4.
• Start blue: Row 1 (1 blue, rem=5), Row 2 (2 red, rem=2), Row 3 (3 blue, rem=2), Row 4 (4 red, need 4 but only 2 remain). Stop at 3.
• Answer = 4.

Common mistakes candidates make

• Only trying one starting color: Missing the second configuration leads to a suboptimal answer in many cases.
• Using all balls from one color in the wrong row: Not alternating correctly, or assigning odd rows to the wrong color.
• Integer overflow in triangle number formula: For large inputs, h*(h+1)/2 can overflow 32-bit integers.

Interview preparation tip

For the Array Enumeration interview pattern, always enumerate both starting configurations for alternating-constraint problems. Code a clean helper function simulate(start_color) and call it twice. This pattern applies to many interview problems involving alternating sequences.