3200. Maximum Height of a Triangle LeetCode Solution
In this guide, you will get 3200. Maximum Height of a Triangle LeetCode Solution with the best time and space complexity. The solution to Maximum Height of a Triangle problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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:
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
Complexity Analysis
Time Complexity: O(\log \max(\texttt{red}, \texttt{blue}))
3200. Maximum Height of a Triangle LeetCode Solution in C++
class Solution {
public:
int maxHeightOfTriangle(int red, int blue) {
return max(maxHeight(red, blue), maxHeight(blue, red));
}
private:
// Returns the maximum height of a triangle with the odd levels having `n1`
// balls and the even levels having `n2` balls.
int maxHeight(int n1, int n2) {
// 1 + 3 + ... + h <= n1
// ((1 + h) * (n + 1) / 2) / 2 <= n1
// h <= sqrt(4 * n1) - 1
const int oddHeight = sqrt(4 * n1) - 1;
// 2 + 4 + ... + h <= n2
// ((2 + h) * h / 2) / 2 <= n2
// h <= sqrt(4 * n2 + 1) - 1
const int evenHeight = sqrt(4 * n2 + 1) - 1;
// If the difference between the odd and even heights is >= 1, we can add an
// extra level to the minimum height.
return min(oddHeight, evenHeight) +
(abs(oddHeight - evenHeight) >= 1 ? 1 : 0);
}
}; /* code provided by PROGIEZ */
3200. Maximum Height of a Triangle LeetCode Solution in Java
class Solution {
public int maxHeightOfTriangle(int red, int blue) {
return Math.max(maxHeight(red, blue), maxHeight(blue, red));
}
// Returns the maximum height of a triangle with the odd levels having `n1`
// balls and the even levels having `n2` balls.
private int maxHeight(int n1, int n2) {
// 1 + 3 + ... + h <= n1
// ((1 + h) * (n + 1) / 2) / 2 <= n1
// h <= sqrt(4 * n1) - 1
final int oddHeight = (int) Math.sqrt(4 * n1) - 1;
// 2 + 4 + ... + h <= n2
// ((2 + h) * h / 2) / 2 <= n2
// h <= sqrt(4 * n2 + 1) - 1
final int evenHeight = (int) Math.sqrt(4 * n2 + 1) - 1;
// If the difference between the odd and even heights is >= 1, we can add an
// extra level to the minimum height.
return Math.min(oddHeight, evenHeight) + (Math.abs(oddHeight - evenHeight) >= 1 ? 1 : 0);
}
} // code provided by PROGIEZ
3200. Maximum Height of a Triangle LeetCode Solution in Python
class Solution:
def maxHeightOfTriangle(self, red: int, blue: int) -> int:
return max(self._maxHeight(red, blue),
self._maxHeight(blue, red))
def _maxHeight(self, n1: int, n2: int) -> int:
"""
Returns the maximum height of a triangle with the odd levels having `n1`
balls and the even levels having `n2` balls.
"""
# 1 + 3 + ... + h <= n1
# ((1 + h) * (n + 1) / 2) / 2 <= n1
# h <= sqrt(4 * n1) - 1
oddHeight = math.isqrt(4 * n1) - 1
# 2 + 4 + ... + h <= n2
# ((2 + h) * h / 2) / 2 <= n2
# h <= sqrt(4 * n2 + 1) - 1
evenHeight = math.isqrt(4 * n2 + 1) - 1
# If the difference between the odd and even heights is >= 1, we can add an
# extra level to the minimum height.
return min(oddHeight, evenHeight) + (1 if abs(oddHeight - evenHeight) >= 1
else 0) # code by PROGIEZ
