Problem Description

You have two types of colored balls: red balls and blue balls. Your task is to arrange these balls into a triangular pattern where:

• The 1st row contains 1 ball
• The 2nd row contains 2 balls
• The 3rd row contains 3 balls
• And so on...

Each row must contain balls of only one color (either all red or all blue), and no two adjacent rows can have the same color. This means if row 1 is red, row 2 must be blue, row 3 must be red, and the pattern continues alternating.

Given the count of red and blue balls available, you need to find the maximum possible height of the triangle you can build following these rules.

For example, if you have 2 red balls and 4 blue balls:

• You could start with 1 red ball in row 1
• Then 2 blue balls in row 2
• Then you'd need 3 red balls for row 3, but you only have 1 red ball left
• So the maximum height would be 2 rows

Alternatively:

• You could start with 1 blue ball in row 1
• Then 2 red balls in row 2
• Then 3 blue balls in row 3 (you have 3 blue balls remaining)
• You'd need 4 red balls for row 4, but you have no red balls left
• So this arrangement gives you a height of 3 rows

The answer would be 3, the maximum of the two possibilities.

Intuition

The key insight is that we only have two possible starting configurations: either we start with a red ball in the first row, or we start with a blue ball in the first row. Once we decide the color of the first row, the entire pattern is determined due to the alternating color requirement.

If we start with red, the pattern would be:

• Row 1: 1 red ball
• Row 2: 2 blue balls
• Row 3: 3 red balls
• Row 4: 4 blue balls
• And so on...

If we start with blue, the pattern would be:

• Row 1: 1 blue ball
• Row 2: 2 red balls
• Row 3: 3 blue balls
• Row 4: 4 red balls
• And so on...

Notice that one color will be used for rows 1, 3, 5, 7... (consuming 1 + 3 + 5 + 7 + ... balls), while the other color will be used for rows 2, 4, 6, 8... (consuming 2 + 4 + 6 + 8 + ... balls).

Since we want to maximize the height, we should try both possibilities and see which one allows us to build higher. For each starting color, we keep building rows as long as we have enough balls of the required color for the next row. We alternate between colors after each row and stop when we can't form the next complete row.

The simulation approach naturally follows from this observation: try both starting colors, simulate the building process for each, and return the maximum height achieved.

Solution Approach

The implementation uses a simulation approach where we try both possible starting colors and track the maximum height achieved.

The algorithm works as follows:

1. Try both starting configurations: The outer loop for k in range(2) represents the two possibilities - starting with red (k=0) or starting with blue (k=1).

2. Initialize for each attempt:

   • Create a list c = [red, blue] to track remaining balls of each color
   • Set i = 1 (the number of balls needed for the current row)
   • Set j = k (the index indicating which color to use, where j=0 means red and j=1 means blue)

3. Build the triangle row by row:

   • The condition while i <= c[j] checks if we have enough balls of the current color to build row i
   • If yes, we use i balls: c[j] -= i
   • Switch to the other color for the next row: j ^= 1 (XOR operation toggles between 0 and 1)
   • Update the maximum height: ans = max(ans, i)
   • Move to the next row: i += 1

4. Return the maximum height found across both starting configurations.

The XOR operation j ^= 1 is a clever way to alternate between colors:

• If j = 0, then j ^= 1 makes j = 1
• If j = 1, then j ^= 1 makes j = 0

This ensures we alternate colors between consecutive rows as required by the problem constraints.

The time complexity is O(sqrt(n)) where n is the total number of balls, since the height of the triangle grows approximately as the square root of the total balls used. The space complexity is O(1) as we only use a few variables to track the state.

Example Walkthrough

Let's walk through an example with red = 2 and blue = 4 balls.

First attempt: Starting with red (k=0)

• Initialize: c = [2, 4], i = 1, j = 0 (using red)
• Row 1: Need 1 red ball, have 2. Use 1 red → c = [1, 4], switch color j = 1, height = 1, next row i = 2
• Row 2: Need 2 blue balls, have 4. Use 2 blue → c = [1, 2], switch color j = 0, height = 2, next row i = 3
• Row 3: Need 3 red balls, have 1. Cannot build this row. Stop.
• Maximum height with red start: 2

Second attempt: Starting with blue (k=1)

• Initialize: c = [2, 4], i = 1, j = 1 (using blue)
• Row 1: Need 1 blue ball, have 4. Use 1 blue → c = [2, 3], switch color j = 0, height = 1, next row i = 2
• Row 2: Need 2 red balls, have 2. Use 2 red → c = [0, 3], switch color j = 1, height = 2, next row i = 3
• Row 3: Need 3 blue balls, have 3. Use 3 blue → c = [0, 0], switch color j = 0, height = 3, next row i = 4
• Row 4: Need 4 red balls, have 0. Cannot build this row. Stop.
• Maximum height with blue start: 3

Final answer: max(2, 3) = 3

The triangle would look like:

    B        (1 blue)
   R R       (2 red)
  B B B      (3 blue)

This demonstrates how trying both starting colors and simulating the building process helps find the optimal arrangement.

Solution Implementation

Time and Space Complexity

The time complexity is O(√n), where n = max(red, blue) represents the maximum number of balls of either color.

The algorithm simulates building a triangle row by row, where each row i requires i balls. The loop continues until we cannot place the required number of balls for the current row. The maximum number of rows we can build is bounded by the equation 1 + 2 + 3 + ... + h ≤ n, which gives us h(h+1)/2 ≤ n. Solving for h, we get h ≤ √(2n), thus h = O(√n).

Since we run this simulation twice (once starting with each color), and each simulation runs for at most O(√n) iterations, the overall time complexity remains O(√n).

The space complexity is O(1) as the algorithm only uses a constant amount of extra space. The variables ans, i, j, k, and the array c (which always contains exactly 2 elements) all require constant space regardless of the input size.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Not Considering Both Starting Colors

A common mistake is to only try one starting configuration (either red or blue first) and miss the optimal solution that might come from starting with the other color.

Incorrect approach:

def maxHeightOfTriangle(self, red: int, blue: int) -> int:
    # Only trying red first
    height = 0
    row = 1
    while True:
        if row % 2 == 1:  # Odd rows use red
            if red >= row:
                red -= row
                height += 1
            else:
                break
        else:  # Even rows use blue
            if blue >= row:
                blue -= row
                height += 1
            else:
                break
        row += 1
    return height

Solution: Always try both starting colors and take the maximum, as shown in the correct implementation.

2. Modifying Original Input Values

Another pitfall is directly modifying the input parameters instead of working with copies, which could cause issues if the function needs to be called multiple times or if the original values are needed later.

Incorrect approach:

def maxHeightOfTriangle(self, red: int, blue: int) -> int:
    max_height = 0
    for k in range(2):
        row = 1
        color_idx = k
        # Directly modifying input parameters - BAD!
        while row <= (red if color_idx == 0 else blue):
            if color_idx == 0:
                red -= row  # Modifying original red value
            else:
                blue -= row  # Modifying original blue value
            max_height = max(max_height, row)
            color_idx ^= 1
            row += 1
    return max_height

Solution: Create a copy of the values for each simulation attempt, as done with available_balls = [red, blue] in the correct implementation.

3. Off-by-One Error in Height Tracking

Some might incorrectly track the height by counting the next row that couldn't be built rather than the last successfully built row.

Incorrect approach:

def maxHeightOfTriangle(self, red: int, blue: int) -> int:
    max_height = 0
    for k in range(2):
        available = [red, blue]
        row = 1
        color_idx = k
        while row <= available[color_idx]:
            available[color_idx] -= row
            color_idx ^= 1
            row += 1
        # Wrong: returning row instead of row-1
        max_height = max(max_height, row)  # This is the row we COULDN'T build
    return max_height

Solution: Update max_height immediately after successfully placing balls in a row, before incrementing the row counter, as shown in the correct implementation with max_height = max(max_height, row_number) placed before row_number += 1.