Is Maximum Height of a Triangle easy or hard?

Maximum Height of a Triangle is classified as an Easy problem. The logic involves simple greedy simulation and arithmetic series formulas. The challenge mainly lies in recognizing the alternating color pattern and computing row requirements correctly.

Maximum Height of a Triangle Python/Java solution

Python, Java, C++, and JavaScript implementations typically simulate rows greedily or apply binary search on the height. Both versions only track remaining red and blue counts and compute required blocks per row, keeping the space complexity O(1).

How to solve Maximum Height of a Triangle in O(log n)?

Use binary search on the possible triangle height. For each candidate height h, compute the number of blocks needed for odd and even rows using arithmetic series formulas. Check both starting configurations (red first or blue first). If the required blocks fit within the available counts, increase the search range; otherwise decrease it.

What is the best approach for Maximum Height of a Triangle?

The greedy row simulation is the most intuitive approach. Simulate building rows one by one while alternating colors and subtracting the required blocks for each row. Try both starting colors and take the maximum height. This runs in about O(sqrt(n)) time because the triangle height grows roughly with the square root of the total blocks.

Is Maximum Height of a Triangle asked at Google/Amazon/Meta?

The problem pattern appears in interviews at companies like Amazon and Google under greedy simulation or binary-search-on-answer categories. Interviewers often expect candidates to first simulate the process and then recognize the mathematical pattern for optimization.

What data structure is used in Maximum Height of a Triangle?

No complex data structures are required. The solution relies on simple arithmetic calculations and iterative checks. The core idea is enumeration of rows or binary search on the answer combined with constant-time math formulas.

What is the time complexity of Maximum Height of a Triangle?

The greedy simulation runs in O(h) time where h is the triangle height, which is approximately O(sqrt(red + blue)). A binary search optimization reduces the complexity to O(log n) by searching for the largest feasible height and checking color requirements using closed-form formulas.

Description Hints 2 Solution Video 4:54

3200. Maximum Height of a Triangle

Easy44.8% acceptance1 company

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 1^st row will have 1 ball, the 2^nd row will have 2 balls, the 3^rd 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:

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

Asked at 1 company

Salesforce

Topics

Array Enumeration

Hints open one at a time

Hint 1

Count the max height using both possibilities. That is, red ball as top and blue ball as top.

Hint 2

For counting the max height, use a simple for loop and remove the number of balls required at this level.

4:54

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def maxHeightOfTriangle(self, red: int, blue: int) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3Case 4

Input

2
4

Input

2
1

Input

1
1

Input

10
1

Your code is saved on this device.Solution