# Maximum Height of a Triangle
**Difficulty:** EASY
[External](https://leetcode.com/problems/maximum-height-of-a-triangle)
Canonical: https://scaleengineer.com/dsa/problems/maximum-height-of-a-triangle
**Patterns:** [Enumeration](https://scaleengineer.com/dsa/patterns/enumeration)
**Data structures:** Array
---
## Problem
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.

**Example 1:**

**Input:** red = 2, blue = 4

**Output:** 3

**Explanation:**

![](https://assets.glich.co/dsa/maximum-height-of-a-triangle/image0.png)

The only possible arrangement is shown above.

**Example 2:**

**Input:** red = 2, blue = 1

**Output:** 2

**Explanation:**

![](https://assets.glich.co/dsa/maximum-height-of-a-triangle/image1.png)  
The only possible arrangement is shown above.

**Example 3:**

**Input:** red = 1, blue = 1

**Output:** 1

**Example 4:**

**Input:** red = 10, blue = 1

**Output:** 2

**Explanation:**

![](https://assets.glich.co/dsa/maximum-height-of-a-triangle/image2.png)  
The only possible arrangement is shown above.

**Constraints:**

* `1 <= red, blue <= 100`

# Approaches
## Iterative Simulation
This approach directly simulates the process of building the triangle. Since there are two possible ways to start (with a red ball row or a blue ball row), we simulate both scenarios and take the maximum height achieved. We greedily add rows one by one as long as we have enough balls of the required color.
**Time:** O(sqrt(red + blue)) - The total number of balls used for a triangle of height `h` is `1 + 2 + ... + h = h*(h+1)/2`. If the total balls are `N = red + blue`, then `h^2` is roughly `2N`, so the maximum height `h` is `O(sqrt(N))`. The loop runs `h` times. · **Space:** O(1) - We only use a few variables to store the current state (ball counts, height, row number).
**Pros:** Simple to understand and implement.; Very efficient for the given constraints, as the maximum height is small.
**Cons:** Asymptotically slower than the binary search approach, although the difference is negligible given the problem's constraints.
### Explanation
We can model the construction of the triangle row by row. The key constraints are that row `i` requires `i` balls, all balls in a row must be the same color, and adjacent rows must have different colors. This leads to two possible coloring patterns:

1.  **Pattern 1:** Odd-numbered rows are red, and even-numbered rows are blue.
2.  **Pattern 2:** Odd-numbered rows are blue, and even-numbered rows are red.

We can write a helper function that takes the counts of balls for odd and even rows and calculates the maximum height possible. We then call this function for both patterns and return the greater of the two heights.

The simulation proceeds iteratively. For a given pattern, we start with `height = 0` and `row = 1`. In a loop, we check if we can build the current `row`. If `row` is odd, we check the ball count for odd rows. If `row` is even, we check the ball count for even rows. If we have enough balls, we subtract the required number, increment the height, and move to the next row. If not, we stop and the current height is the maximum for that pattern.

```java
class Solution {
    public int maxHeightOfTriangle(int red, int blue) {
        // Scenario 1: Odd rows are red, even are blue
        int height1 = calculateHeight(red, blue);
        // Scenario 2: Odd rows are blue, even are red
        int height2 = calculateHeight(blue, red);
        return Math.max(height1, height2);
    }

    private int calculateHeight(int oddColorBalls, int evenColorBalls) {
        int height = 0;
        int row = 1;
        while (true) {
            if (row % 2 != 0) { // Odd row
                if (oddColorBalls >= row) {
                    oddColorBalls -= row;
                } else {
                    break;
                }
            } else { // Even row
                if (evenColorBalls >= row) {
                    evenColorBalls -= row;
                } else {
                    break;
                }
            }
            height++;
            row++;
        }
        return height;
    }
}
```
### Algorithm
- Simulate the triangle construction for two separate scenarios: one starting with a red row and another starting with a blue row.
- For each scenario, iterate row by row, starting from row 1.
- In each iteration `i`, check if there are enough balls (`i` balls) of the required color for that row.
- If yes, subtract the balls, increment the height, and continue to the next row.
- If no, the construction for that scenario stops, and the current height is the maximum for that scenario.
- The final answer is the maximum height obtained from the two scenarios.

## Binary Search on the Height
A more optimized approach uses binary search on the height of the triangle. The core idea is that the possibility of forming a triangle of a certain height is a monotonic function. If we can build a triangle of height `h`, we can definitely build one of height `h-1`. This allows us to efficiently search for the maximum possible height.
**Time:** O(log(max_height)) - The search space for the height is up to `red + blue`. The binary search takes logarithmic time relative to the size of this search space. Since `max_height` is `O(sqrt(red+blue))`, the complexity is `O(log(sqrt(red+blue)))`, which simplifies to `O(log(red+blue))`. The `isPossible` check is O(1). · **Space:** O(1) - The binary search and helper function use a constant amount of extra space.
**Pros:** Asymptotically the most efficient approach.; Scales well even if the constraints on `red` and `blue` were much larger.
**Cons:** Slightly more complex to reason about and implement compared to the direct simulation.; Requires careful handling of formulas and potential integer overflows for ball counts.
### Explanation
We can binary search for the maximum height `h`. For a given `h`, we need an `O(1)` way to check if it's possible to construct such a triangle. A triangle of height `h` is possible if we have enough red and blue balls for one of the two coloring patterns.

Let's analyze the ball requirements for a height `h`:
- Number of odd rows: `(h + 1) / 2`
- Number of even rows: `h / 2`
- Balls for odd rows (sum of first `k` odd numbers `1, 3, ...`): `k^2`, where `k = (h+1)/2`.
- Balls for even rows (sum of first `k` even numbers `2, 4, ...`): `k*(k+1)`, where `k = h/2`.

Our `isPossible(h)` function will calculate these required ball counts and check against the available `red` and `blue` balls:
1.  **Case 1 (Start Red):** Check if `red >= balls_for_odd_rows` and `blue >= balls_for_even_rows`.
2.  **Case 2 (Start Blue):** Check if `blue >= balls_for_odd_rows` and `red >= balls_for_even_rows`.

If either case is true, a triangle of height `h` is possible. The binary search algorithm will use this check to narrow down the search space and find the maximum `h`.

```java
class Solution {
    public int maxHeightOfTriangle(int red, int blue) {
        int low = 0, high = 200; // A safe upper bound for height
        int ans = 0;
        while (low <= high) {
            int h = low + (high - low) / 2;
            if (isPossible(h, red, blue)) {
                ans = h;
                low = h + 1; // Try for a larger height
            } else {
                high = h - 1; // Height is too large
            }
        }
        return ans;
    }

    private boolean isPossible(int h, int red, int blue) {
        if (h == 0) {
            return true;
        }
        long oddRows = (h + 1) / 2;
        long evenRows = h / 2;

        long ballsForOddRows = oddRows * oddRows;
        long ballsForEvenRows = evenRows * (evenRows + 1);

        // Case 1: Odd rows are red, even rows are blue
        if (red >= ballsForOddRows && blue >= ballsForEvenRows) {
            return true;
        }

        // Case 2: Odd rows are blue, even rows are red
        if (blue >= ballsForOddRows && red >= ballsForEvenRows) {
            return true;
        }

        return false;
    }
}
```
### Algorithm
- The problem has a monotonic property: if a triangle of height `h` is possible, any triangle of height less than `h` is also possible.
- This allows us to use binary search on the answer (the height `h`).
- We define a search space for `h`, for example, from `0` to `200`.
- For each `mid` value in the binary search, we check if a triangle of height `mid` is feasible using a helper function `isPossible(h)`.
- The `isPossible(h)` function calculates the total balls needed for each color for a height `h` and checks against the available `red` and `blue` balls for both starting color scenarios.
- If `isPossible(mid)` is true, we store `mid` as a potential answer and search for a larger height (`low = mid + 1`).
- If false, we search for a smaller height (`high = mid - 1`).

# Solutions
### Java

```java
class Solution {
public
  int maxHeightOfTriangle(int red, int blue) {
    int ans = 0;
    for (int k = 0; k < 2; ++k) {
      int[] c = {red, blue};
      for (int i = 1, j = k; i <= c[j]; j ^= 1, ++i) {
        c[j] -= i;
        ans = Math.max(ans, i);
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int maxHeightOfTriangle(int red, int blue) {
    int ans = 0;
    for (int k = 0; k < 2; ++k) {
      int c[2] = {red, blue};
      for (int i = 1, j = k; i <= c[j]; j ^= 1, ++i) {
        c[j] -= i;
        ans = max(ans, i);
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def maxHeightOfTriangle(self, red: int, blue: int) -> int: ans = 0 for k in range(2): c = [red, blue] i, j = 1, k while i <= c[j]: c[j] -= i j ^= 1 ans = max(ans, i) i += 1 return ans

```