3200. Maximum Height of a Triangle

Intuition

The problem involves arranging red and blue balls into rows such that each row has an increasing number of balls and adjacent rows alternate colors. The goal is to maximize the height of the triangle formed by these balls.

Approach

1. Recursive Simulation: - We simulate placing rows of balls recursively, alternating between red and blue. - For each row, we decide whether to add red or blue balls based on the current count of available balls of each color. - We continue this process until we cannot add a full row of balls of the chosen color due to lack of balls.
2. Backtracking with Memorization: - To optimize the recursive approach, we use memoization to store results of subproblems (i.e., configurations of remaining red and blue balls). - This avoids redundant calculations and speeds up the computation significantly.
3. Base Cases: - If either color runs out of balls, we cannot form a complete row, so we return the height of the triangle formed so far.
4. Maximization: - At each recursive step, we choose the maximum height achievable by either starting with a row of red balls or a row of blue balls.

Complexity

• Time Complexity: - The time complexity primarily depends on the number of recursive calls, which is bounded by the product of the counts of red and blue balls, O(red * blue). However, with memoization, the effective complexity is reduced significantly for repeated states.
• Space Complexity: - The space complexity is O(red * blue) due to the memoization table used to store results of subproblems.

Code Explanation

Return Statement

return Math.max(solve(red, blue), solve(blue, red));

• Calculates and returns the maximum height of the triangle by taking the maximum of two values: - solve(red, blue): Computes the maximum height starting with red balls. - solve(blue, red): Computes the maximum height starting with blue balls.

Helper Function (`solve`)

var solve = function (a, b) {
    var flag = true;
    for (var i = 1; ; ++i, flag = !flag) {

• Defines a helper function named solve that takes two parameters, a and b, representing the remaining red and blue balls, respectively.
• Uses a for loop to simulate the construction of each row of the triangle.
• flag alternates between true (red) and false (blue) to determine which color of balls to place in each row.

if (flag) {
  if (a < i) return i - 1;
  a -= i;
} else {
  if (b < i) return i - 1;
  b -= i;
}

• Inside the solve function's loop: - Checks if there are enough balls (a >= i for red, b >= i for blue) to form the current row. - If there aren't enough balls, it returns i - 1, which represents the height of the triangle formed so far. - Deducts the used balls (a -= i for red, b -= i for blue) from the respective counters.

Code

C++

class Solution {
public:
    int maxHeightOfTriangle(int red, int blue) {
        return max(solve(red, blue), solve(blue, red));
    }
    
private:
    int solve(int a, int b) {
        bool flag = true;
        for (int i = 1; ; ++i, flag = !flag) {
            if (flag) {
                if (a < i) return i - 1;
                a -= i;
            } else {
                if (b < i) return i - 1;
                b -= i;
            }
        }
    }
};

Python

class Solution:
    def maxHeightOfTriangle(self, red: int, blue: int) -> int:
        return max(self.solve(red, blue), self.solve(blue, red))
    
    def solve(self, a: int, b: int) -> int:
        flag = True
        i = 1
        while True:
            if flag:
                if a < i:
                    return i - 1
                a -= i
            else:
                if b < i:
                    return i - 1
                b -= i
            i += 1
            flag = not flag

Java

class Solution {
    public int maxHeightOfTriangle(int red, int blue) {
        return Math.max(solve(red, blue), solve(blue, red));
    }
    
    private int solve(int a, int b) {
        boolean flag = true;
        for (int i = 1; ; ++i, flag = !flag) {
            if (flag) {
                if (a < i) return i - 1;
                a -= i;
            } else {
                if (b < i) return i - 1;
                b -= i;
            }
        }
    }
}

JavaScript

/**
 * @param {number} red
 * @param {number} blue
 * @return {number}
 */
var maxHeightOfTriangle = function (red, blue) {
  return Math.max(solve(red, blue), solve(blue, red));
};

var solve = function (a, b) {
  var flag = true;
  for (i = 1; ; ++i, flag = !flag) {
    if (flag) {
      if (a < i) return i - 1;
      a -= i;
    } else {
      if (b < i) return i - 1;
      b -= i;
    }
  }
};