LeetCode Weekly Contest 482 Discussion and Solution

Problem-by-Problem Breakdown

Problem 1 - Maximum Score of a Split

• Let prefixSum(i) be the sum of nums[0] + nums[1] + ... + nums[i].
• Let suffixMin(i) be the minimum value among nums[i + 1], nums[i + 2], ..., nums[n - 1].

Approach

Java Code

class Solution {
    public long maximumScore(int[] nums) {
        int n = nums.length;

        int[] minVal = new int[n];
        
        long prefix = 0;
        long ans = Long.MIN_VALUE;

        minVal[n - 1] = nums[n - 1];

        for(int i = n - 2; i >= 0; i--){
            minVal[i] = Math.min(minVal[i + 1], nums[i]);
        }


        for(int i = 0; i < n - 1; i++){
            prefix += nums[i];
            int suffix = minVal[i + 1];

            ans = Math.max(prefix - suffix, ans);
        }

        return ans;
    }
}

Problem 2 - Minimum Cost to Acquire Required Items

• An item of type 1 costs cost1 and contributes 1 unit to the type 1 requirement only.
• An item of type 2 costs cost2 and contributes 1 unit to the type 2 requirement only.
• An item of type 3 costs costBoth and contributes 1 unit to both type 1 and type 2 requirements.

Approach

Java Code

class Solution {
    public long minimumCost(int cost1, int cost2, int costBoth, int need1, int need2) {
        long ans = 0;

        if(need1 == 0 && need2 == 0){
            return 0;
        }

        int commonItems = Math.min(need1, need2);

        need1 -= commonItems;
        need2 -= commonItems;

        if(commonItems > 0){
            ans += 1L * commonItems * Math.min(cost1 + cost2, costBoth);
        }

        if(need1 == 0){
            ans += 1L * need2 * Math.min(cost2, costBoth);
        }

        if(need2 == 0){
            ans += 1L * need1 * Math.min(cost1, costBoth);
        }

        return ans;
    }
}

Problem 3 - Smallest All-Ones Multiple

Approach

Java Code

class Solution {
    public int minAllOneMultiple(int k) {
        Set<Integer> remSet = new HashSet<>();
        
        int rem = 1 % k;
        int count = 1;
        remSet.add(rem);

        while(rem != 0){
            rem = (rem * 10 + 1) % k;
            count++;

            if(remSet.contains(rem)) return -1;
            else remSet.add(rem);
        }

        return count;
    }
}

Problem 4 - Number of Balanced Integers in a Range

• It contains at least two digits.
• The sum of digits at even positions is equal to the sum of digits at odd positions (the leftmost digit has position 1).

Approach

My Contest Experience