We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Height of a Triangle

Number: 3469

Difficulty: Easy

Paid? No

Companies: Salesforce

Problem Description

Given two integers red and blue representing the number of red and blue balls respectively, we want to build a triangle where the 1st row has 1 ball, the 2nd has 2 balls, the 3rd has 3 balls, and so on. Each row must use balls of the same color, and consecutive rows must have different colors. The goal is to determine the maximum possible height (i.e. the number of rows) that can be formed under these conditions.

Key Insights

  • The triangle has rows 1, 2, 3, ..., h requiring a total of h*(h+1)/2 balls.
  • When assigning colors, there are exactly two possible ordering patterns:
    • Starting with red: rows 1, 3, 5, ... use red balls and rows 2, 4, 6, ... use blue balls.
    • Starting with blue: rows 1, 3, 5, ... use blue balls and rows 2, 4, 6, ... use red balls.
  • The sum of the balls in the odd-indexed rows (if there are m such rows) is m² (because the sum of the first m odd numbers equals m²), and the sum in the even-indexed rows (if there are n such rows) is n*(n+1) (because the sum of first n even numbers equals n*(n+1)).
  • For a given height h, we can compute:
    • if starting with red: required_red = (ceil(h/2))² and required_blue = (floor(h/2))*(floor(h/2)+1)
    • if starting with blue: required_blue = (ceil(h/2))² and required_red = (floor(h/2))*(floor(h/2)+1)
  • Since h is small (due to the ball count constraints), we can iterate from 1 upward until neither pattern can be achieved.

Space and Time Complexity

Time Complexity: O(n) where n is the potential triangle height (n is small given constraints). Space Complexity: O(1)

Solution

We approach the problem by trying every possible triangle height h (starting from 1) until the required balls for both color-assignments (starting with red and starting with blue) exceed the available counts. For each h, we calculate:

  • The number of rows using the starting color: m = ceil(h / 2)
  • The number of rows using the alternate color: n = floor(h / 2)

Then, based on the pattern:

  • When starting with red, the red balls needed are m² and blue balls needed are n*(n+1).
  • When starting with blue, the blue balls needed are m² and red balls needed are n*(n+1).

If either ordering is valid (i.e. the required balls for both colors do not exceed the available counts), then h is a valid triangle height. We continue increasing h until neither ordering works, and then the maximum valid h found is returned.

The main trick is to recognize that the sum of odd-indexed row sizes can be computed as m² and even-indexed row sizes as n*(n+1), which allows checking each candidate height in constant time.

Code Solutions

# Python solution:
def maximumTriangleHeight(red, blue):
    max_height = 0
    h = 1
    # iterate while it might be possible to form the triangle
    while True:
        # compute number of rows for the "first color" (m) and "second color" (n)
        m = (h + 1) // 2  # ceil(h/2)
        n = h // 2        # floor(h/2)
        
        # Calculate balls required for each color in both possible starting orders.
        # Starting with red:
        required_red_start_red = m * m           # sum of odd-indexed rows when starting with red
        required_blue_start_red = n * (n + 1)      # sum of even-indexed rows when starting with red
        
        # Starting with blue:
        required_blue_start_blue = m * m           # sum of odd-indexed rows when starting with blue
        required_red_start_blue = n * (n + 1)        # sum of even-indexed rows when starting with blue
        
        # If either ordering can be made with available balls:
        if ((red >= required_red_start_red and blue >= required_blue_start_red) or 
            (red >= required_red_start_blue and blue >= required_blue_start_blue)):
            max_height = h  # update maximum valid height
            h += 1
        else:
            break
    return max_height

# Example usage:
print(maximumTriangleHeight(2, 4))  # Output: 3
print(maximumTriangleHeight(2, 1))  # Output: 2
print(maximumTriangleHeight(1, 1))  # Output: 1
print(maximumTriangleHeight(10, 1)) # Output: 2
← Back to All Questions