Maximum Height of a Triangle

• Simulate the triangle construction for two separate scenarios: one starting with a red row and another starting with a blue row.
• For each scenario, iterate row by row, starting from row 1.
• In each iteration i, check if there are enough balls (i balls) of the required color for that row.
• If yes, subtract the balls, increment the height, and continue to the next row.
• If no, the construction for that scenario stops, and the current height is the maximum for that scenario.
• The final answer is the maximum height obtained from the two scenarios.

We can model the construction of the triangle row by row. The key constraints are that row i requires i balls, all balls in a row must be the same color, and adjacent rows must have different colors. This leads to two possible coloring patterns:

1. Pattern 1: Odd-numbered rows are red, and even-numbered rows are blue.
2. Pattern 2: Odd-numbered rows are blue, and even-numbered rows are red.

We can write a helper function that takes the counts of balls for odd and even rows and calculates the maximum height possible. We then call this function for both patterns and return the greater of the two heights.

The simulation proceeds iteratively. For a given pattern, we start with height = 0 and row = 1. In a loop, we check if we can build the current row. If row is odd, we check the ball count for odd rows. If row is even, we check the ball count for even rows. If we have enough balls, we subtract the required number, increment the height, and move to the next row. If not, we stop and the current height is the maximum for that pattern.

1class Solution {2    public int maxHeightOfTriangle(int red, int blue) {3        // Scenario 1: Odd rows are red, even are blue4        int height1 = calculateHeight(red, blue);5        // Scenario 2: Odd rows are blue, even are red6        int height2 = calculateHeight(blue, red);7        return Math.max(height1, height2);8    }9 10    private int calculateHeight(int oddColorBalls, int evenColorBalls) {11        int height = 0;12        int row = 1;13        while (true) {14            if (row % 2 != 0) { // Odd row15                if (oddColorBalls >= row) {16                    oddColorBalls -= row;17                } else {18                    break;19                }20            } else { // Even row21                if (evenColorBalls >= row) {22                    evenColorBalls -= row;23                } else {24                    break;25                }26            }27            height++;28            row++;29        }30        return height;31    }32}

• The problem has a monotonic property: if a triangle of height h is possible, any triangle of height less than h is also possible.
• This allows us to use binary search on the answer (the height h).
• We define a search space for h, for example, from 0 to 200.
• For each mid value in the binary search, we check if a triangle of height mid is feasible using a helper function isPossible(h).
• The isPossible(h) function calculates the total balls needed for each color for a height h and checks against the available red and blue balls for both starting color scenarios.
• If isPossible(mid) is true, we store mid as a potential answer and search for a larger height (low = mid + 1).
• If false, we search for a smaller height (high = mid - 1).

We can binary search for the maximum height h. For a given h, we need an O(1) way to check if it's possible to construct such a triangle. A triangle of height h is possible if we have enough red and blue balls for one of the two coloring patterns.

Let's analyze the ball requirements for a height h:

• Number of odd rows: (h + 1) / 2
• Number of even rows: h / 2
• Balls for odd rows (sum of first k odd numbers 1, 3, ...): k^2, where k = (h+1)/2.
• Balls for even rows (sum of first k even numbers 2, 4, ...): k*(k+1), where k = h/2.

Our isPossible(h) function will calculate these required ball counts and check against the available red and blue balls:

1. Case 1 (Start Red): Check if red >= balls_for_odd_rows and blue >= balls_for_even_rows.
2. Case 2 (Start Blue): Check if blue >= balls_for_odd_rows and red >= balls_for_even_rows.

If either case is true, a triangle of height h is possible. The binary search algorithm will use this check to narrow down the search space and find the maximum h.

1class Solution {2    public int maxHeightOfTriangle(int red, int blue) {3        int low = 0, high = 200; // A safe upper bound for height4        int ans = 0;5        while (low <= high) {6            int h = low + (high - low) / 2;7            if (isPossible(h, red, blue)) {8                ans = h;9                low = h + 1; // Try for a larger height10            } else {11                high = h - 1; // Height is too large12            }13        }14        return ans;15    }16 17    private boolean isPossible(int h, int red, int blue) {18        if (h == 0) {19            return true;20        }21        long oddRows = (h + 1) / 2;22        long evenRows = h / 2;23 24        long ballsForOddRows = oddRows * oddRows;25        long ballsForEvenRows = evenRows * (evenRows + 1);26 27        // Case 1: Odd rows are red, even rows are blue28        if (red >= ballsForOddRows && blue >= ballsForEvenRows) {29            return true;30        }31 32        // Case 2: Odd rows are blue, even rows are red33        if (blue >= ballsForOddRows && red >= ballsForEvenRows) {34            return true;35        }36 37        return false;38    }39}