Maximum Height of a Triangle - Practice Coding Problems

Maximum Height of a Triangle - Problem

Array Enumeration Easy

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.

Input & Output

Example 1 — Basic Case

$ Input: red = 2, blue = 1

› Output: 2

💡 Note: Start with red (row 1: 1 red ball), then blue (row 2: 2 blue balls, but we only have 1). So we can't complete row 2 with blue. If we start with blue (row 1: 1 blue ball), then red (row 2: need 2 red balls, we have 2), we get height 2.

Example 2 — Equal Balls

$ Input: red = 1, blue = 1

› Output: 1

💡 Note: We can only build 1 row using either color. Row 2 would need 2 balls but we only have 1 of the other color.

Example 3 — Larger Input

$ Input: red = 10, blue = 1

› Output: 2

💡 Note: Start with blue (row 1: 1 blue ball), then red (row 2: 2 red balls). We have enough red balls but can't continue to row 3 which would need 3 blue balls.

Constraints

1 ≤ red ≤ 100
1 ≤ blue ≤ 100

Visualization

Tap to expand

Understanding the Visualization

Input

Two integers: red balls and blue balls

Build Triangle

Each row needs i balls, adjacent rows different colors

Find Maximum

Try both starting colors, return max height

Key Takeaway

🎯 Key Insight: Always try both starting colors since one arrangement might be significantly better than the other

Asked in

M Microsoft 15 G Google 12

The key insight is to try both starting colors since the optimal arrangement might begin with either red or blue. We can either simulate the triangle building process or use mathematical formulas for odd/even rows. Best approach uses simulation for simplicity. Time: O(√n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Simulation	O(√n)	O(1)	Try both starting colors and simulate building the triangle row by row
Mathematical Formula	O(1)	O(1)	Use mathematical formulas to calculate maximum possible rows for each pattern

Brute Force Simulation — Algorithm Steps

Try starting with red color first
Simulate row by row, alternating colors
Try starting with blue color first
Return maximum height achieved

Visualization

Tap to expand

Step-by-Step Walkthrough

Try Red First

Start with red, alternate colors

Try Blue First

Start with blue, alternate colors

Take Maximum

Return the better result

Code -

solution.c — C

#include <stdio.h>

int simulate(int color1Balls, int color2Balls) {
    int height = 0;
    int row = 1;
    int useColor1 = 1;
    
    while (1) {
        if (useColor1) {
            if (color1Balls >= row) {
                color1Balls -= row;
                height++;
                row++;
                useColor1 = 0;
            } else {
                break;
            }
        } else {
            if (color2Balls >= row) {
                color2Balls -= row;
                height++;
                row++;
                useColor1 = 1;
            } else {
                break;
            }
        }
    }
    return height;
}

int solution(int red, int blue) {
    int option1 = simulate(red, blue);
    int option2 = simulate(blue, red);
    return option1 > option2 ? option1 : option2;
}

int main() {
    int red, blue;
    scanf("%d", &red);
    scanf("%d", &blue);
    printf("%d\n", solution(red, blue));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(√n)

We iterate through rows until we run out of balls. Maximum rows is roughly √(red+blue)

✓ Linear Growth

Space Complexity

O(1)

Only using a few variables to track current state

✓ Linear Space

23.4K Views

Medium Frequency

~15 min Avg. Time

856 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Simulation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler