Algorithm: Leetcode Contest 391

3100. Water Bottles II

Solution

class Solution {
    public int maxBottlesDrunk(int numBottles, int numExchange) {
        // empty bottle 
        
        
        
        // end condition
        // full bottle = 0
        // empty bottle < numExchange
        
        int res = 0;
        int emptyBottle = 0;
        while (!(numBottles == 0 && emptyBottle < numExchange)) {
            res += numBottles;
            emptyBottle += numBottles;
            numBottles = 0;
            while(!(emptyBottle < numExchange)) {
                emptyBottle -= numExchange++;
                numBottles++;
            }
        }
        
        
        return res;
    }
}

No hard, as long as figure out the iteration and final condition, this is an easy challenge

3101. Count Alternating Subarrays

Solution

class Solution {
    public long countAlternatingSubarrays(int[] nums) {
        // understand how many arrays starting from each element 
        
        long res = 0;
        
        int[] acc = new int[nums.length];
        
        acc[nums.length - 1] = 1;
        int index = nums.length - 2;
        
        while (index >= 0) {
            acc[index] = 1;
            if(nums[index] != nums[index + 1]) {
                 acc[index] += acc[index + 1]; 
            }
            index--;
        }
        
        for(int count : acc) {
            res += count;
        }
        
        return res;
    }
}

Retro

When encountering N^2 solution on array, think about if there is any faster solution (N)