Maximum Height of a Triangle

Difficulty: Easy | Acceptance: 44.40% | Paid: No Topics: Array, Enumeration

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:

1. The first row of the triangle has 1 ball.
2. The second row of the triangle has 2 balls.
3. The k-th row of the triangle has k balls.
4. All balls in a row have the same color.
5. Adjacent rows have different colors.

Return the maximum possible height of the triangle.

• Examples
• Constraints
• Simulation Approach
• Binary Search Approach

Examples

Example 1

Input:

red = 2, blue = 4

Output:

3

Explanation: The only possible arrangement is shown above.

Example 2

Input:

red = 2, blue = 1

Output:

2

Explanation: 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: The only possible arrangement is shown above.

Constraints

- 1 <= red, blue <= 100

Simulation Approach

Intuition We can simulate the process of building the triangle row by row. Since the first row can be either Red or Blue, we try both possibilities and return the maximum height achieved.

Steps

• Create a helper function calculateHeight(color1, color2) that simulates building the triangle starting with color1.
• Initialize height = 0 and row = 1.
• Loop while true:
  • If row is odd, check if we have enough balls of color1 (i.e., color1 >= row). If yes, subtract row from color1. If no, break the loop.
  • If row is even, check if we have enough balls of color2 (i.e., color2 >= row). If yes, subtract row from color2. If no, break the loop.
  • Increment height and row.
• Return the maximum of calculateHeight(red, blue) and calculateHeight(blue, red).

class Solution:
    def maxHeightOfTriangle(self, red: int, blue: int) -> int:
        def solve(c1, c2):
            h = 0
            i = 1
            while True:
                if i % 2 == 1:
                    if c1 >= i:
                        c1 -= i
                    else:
                        break
                else:
                    if c2 >= i:
                        c2 -= i
                    else:
                        break
                h += 1
                i += 1
            return h
        return max(solve(red, blue), solve(blue, red))

Complexity

• Time: O(√N) - The loop runs until we run out of balls. The height is proportional to the square root of the total number of balls.
• Space: O(1) - We use a constant amount of extra space.
• Notes: Simple and easy to implement. Efficient enough given the constraints.

Binary Search Approach

Intuition The number of balls required grows quadratically with the height of the triangle. We can use binary search to efficiently find the maximum height k such that the required balls for both colors are less than or equal to the available balls.

Steps

• Define a helper function canForm(k, c1, c2) which checks if a triangle of height k can be formed starting with color c1 for the first row.
• In canForm(k, c1, c2):
  • Calculate the number of odd rows: oddRows = (k + 1) / 2.
  • Calculate the number of even rows: evenRows = k / 2.
  • The sum of balls for odd rows (1 + 3 + 5 + …) is oddRows * oddRows.
  • The sum of balls for even rows (2 + 4 + 6 + …) is evenRows * (evenRows + 1).
  • Check if c1 >= oddSum and c2 >= evenSum.
• Perform binary search for k in the range [0, 2 * 10⁹] (a safe upper bound).
• Return the maximum k found for both starting colors (Red first or Blue first).

class Solution:
    def maxHeightOfTriangle(self, red: int, blue: int) -> int:
        def check(k, c1, c2):
            odd = (k + 1) // 2
            even = k // 2
            need1 = odd * odd
            need2 = even * (even + 1)
            return c1 >= need1 and c2 >= need2

        def search(c1, c2):
            l, r = 0, 2 * 10**9
            ans = 0
            while l <= r:
                mid = (l + r) // 2
                if check(mid, c1, c2):
                    ans = mid
                    l = mid + 1
                else:
                    r = mid - 1
            return ans

        return max(search(red, blue), search(blue, red))

Complexity

• Time: O(log N) - Binary search performs log(N) iterations, where N is the upper bound for the height.
• Space: O(1) - We use a constant amount of extra space.
• Notes: More efficient for very large constraints compared to simulation, though both are acceptable here. Requires careful handling of integer overflow in languages like Java and C++.