Algorithm: Leetcode Contest 404

3200. Maximum Height of a Triangle

Solution

class Solution {
    public int maxHeightOfTriangle(int red, int blue) {
        int redRoot = getHeightForRoot(red, blue);
        int blueRoot = getHeightForRoot(blue, red);
        
        return Math.max(redRoot, blueRoot);
    }
    
    private int getHeightForRoot(int color, int anotherColor) {
        
        int height = 0, nextHeight = 1;
        boolean flag = true;
        while(true) {
            if (flag) {
                color -= nextHeight;
            } else {
                anotherColor -= nextHeight;
            }
            
            if (color >= 0 && anotherColor >= 0) {
                height = nextHeight;
                nextHeight++;
                flag = !flag;
            } else {
                break;
            }
        }
        
        return height;
    }
}

Retro

this challenge is relatively harder than before.

several learnings

1. how to handle height and nextHeight is not straightforward
2. extract the duplicate code into separate function

3201. Find the Maximum Length of Valid Subsequence I

Solution

class Solution {
    public int maximumLength(int[] nums) {
        int alt = 0, odd = 0, even = 0;
        int flag = nums[0] % 2;

        for(int num: nums) {
            if (num % 2 == 0) {
                even++;
            } else {
                odd++;
            }

            if (num % 2 == flag) {
                alt++;
                flag = 1 - flag;
            }
        }

        return Math.max(alt, Math.max(odd, even));
    }
}

Retro

1. didn’t recognize this is a parity issue, thought it’s a DP problem.
2. problem is I didn’t deeply understand the meaning of the provided format, just think it’s normal while actually it indicate the odd & even direction