Skip to content

3200. Maximum Height of a Triangle 👍

  • Time: $O(\log \max(\texttt{red}, \texttt{blue}))$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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);
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
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);
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
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)