Leetcode Problem:

• Put Marbles in Bags

Summary

• The problem requires finding the difference between the maximum and minimum scores of marble distributions given an array of weights and the number of bags.

Approach

• The solution uses a prefix sum array to efficiently calculate the sum of weights for each subarray
• It then sorts the prefix sum array and iterates through it to calculate the minimum and maximum scores by adding the weights at specific indices
• The difference between the maximum and minimum scores is then returned.

Complexity

• O(n log n) due to the sorting of the prefix sum array, where n is the number of weights.

Solution Code:

class Solution {
public:
    long long putMarbles(vector& weights, int k) {
        if(weights.size() == k) return 0;
        vector prefixSum;
        long long sum = weights[0];
        for(int i = 1 ; i < weights.size(); i++){
            sum += weights[i];
            prefixSum.push_back(sum);
            sum -= weights[i-1];
        }
        sort(prefixSum.begin(), prefixSum.end());

        long long maxScore = weights[0] + weights[weights.size() - 1];
        long long minScore = weights[0] + weights[weights.size() - 1];
        for(int i = 0; i < k - 1; i++){
            minScore += prefixSum[i];
            maxScore += prefixSum[prefixSum.size() - 1 - i];
        }

        return maxScore - minScore;
    }
};

Leetcode Problem:

• Partition Labels

Summary

• Partitioning a string into parts where each letter appears in at most one part

Approach

• Use a hashmap to store the last index of each character, then iterate through the string, updating the end index and adding the current part size to the result vector when the end index matches the current index

Complexity

• O(n) where n is the length of the string

Explanation

• The approach is to first store the last index of each character in a hashmap
• Then, we iterate through the string, updating the end index whenever we encounter a character
• When the end index matches the current index, we know we've reached the end of the current part, so we add its size to the result vector and reset the start and end indices
• This way, we ensure that each letter appears in at most one part and that the resultant string is the original input string

Solution Code:

class Solution {
public:
    int lastIdx[256];
    vector partitionLabels(string s) {
        for(int i = 0 ; i < s.size(); i++){
            lastIdx[s[i]] = i;
        }

        vector ans;
        int start = 0;
        int end = 0;
        for(int i = 0 ; i < s.size(); i++){
            end = max(end, lastIdx[s[i]]);
            if(end == i){
                ans.push_back(end - start + 1);
                start = end = end +1;
            }
        }
        return ans;
    }
};

Leetcode Problem:

• Apply Operations to Maximize Score

Summary

• The problem requires to find the maximum possible score that can be obtained by applying at most k operations on an array of positive integers
• The operations involve choosing a non-empty subarray with the highest prime score and multiplying the score by the chosen element.

Approach

• The solution uses the Sieve of Eratosthenes to generate prime numbers up to the maximum element in the array
• It then calculates the prime score for each number in the array and uses a stack to find the dominant indices for each number
• The maximum possible score is then calculated by raising the element with the maximum value to the power of the number of operations available.

Complexity

• O(n log n) due to the Sieve of Eratosthenes and O(n log n) due to the sorting of the array
• The power function has a complexity of O(log n) and the overall complexity is dominated by the sorting and Sieve of Eratosthenes steps.

Solution Code:

class Solution {
public:
    const int MOD = 1e9 + 7;

    int maximumScore(vector& nums, int k) {
        int n = nums.size();
        vector primeScores(n, 0);

        // Find the maximum element in nums to determine the range for prime
        // generation
        int maxElement = 0;
        for (int index = 0; index < n; index++) {
            maxElement = max(maxElement, nums[index]);
        }

        // Get all prime numbers up to maxElement using the Sieve of
        // Eratosthenes
        vector primes = getPrimes(maxElement);

        // Calculate the prime score for each number in nums
        for (int index = 0; index < n; index++) {
            int num = nums[index];

            // Iterate over the generated primes to count unique prime factors
            for (int prime : primes) {
                if (prime * prime > num)
                    break;  // Stop early if prime^2 exceeds num
                if (num % prime != 0)
                    continue;  // Skip if the prime is not a factor

                primeScores[index]++;  // Increment prime score for the factor
                while (num % prime == 0)
                    num /= prime;  // Remove all occurrences of this factor
            }

            // If num is still greater than 1, it is a prime number itself
            if (num > 1) primeScores[index]++;
        }

        // Initialize next and previous dominant index arrays
        vector nextDominant(n, n);
        vector prevDominant(n, -1);

        // Stack to store indices for a monotonic decreasing prime score
        stack decreasingPrimeScoreStack;

        // Calculate the next and previous dominant indices for each number
        for (int index = 0; index < n; index++) {
            // While the stack is not empty and the current prime score is
            // greater than the stack's top, update nextDominant
            while (!decreasingPrimeScoreStack.empty() &&
                   primeScores[decreasingPrimeScoreStack.top()] <
                       primeScores[index]) {
                int topIndex = decreasingPrimeScoreStack.top();
                decreasingPrimeScoreStack.pop();

                // Set the next dominant element for the popped index
                nextDominant[topIndex] = index;
            }

            // If the stack is not empty, set the previous dominant element for
            // the current index
            if (!decreasingPrimeScoreStack.empty())
                prevDominant[index] = decreasingPrimeScoreStack.top();

            // Push the current index onto the stack
            decreasingPrimeScoreStack.push(index);
        }

        // Calculate the number of subarrays in which each element is dominant
        vector numOfSubarrays(n);
        for (int index = 0; index < n; index++) {
            numOfSubarrays[index] = (long long)(nextDominant[index] - index) *
                                    (index - prevDominant[index]);
        }

        // Sort elements in decreasing order based on their values
        vector> sortedArray(n);
        for (int index = 0; index < n; index++) {
            sortedArray[index] = {nums[index], index};
        }

        sort(sortedArray.begin(), sortedArray.end(), greater<>());

        long long score = 1;
        int processingIndex = 0;

        // Process elements while there are operations left
        while (k > 0) {
            // Get the element with the maximum value
            auto [num, index] = sortedArray[processingIndex++];

            // Calculate the number of operations to apply on the current
            // element
            long long operations = min((long long)k, numOfSubarrays[index]);

            // Update the score by raising the element to the power of
            // operations
            score = (score * power(num, operations)) % MOD;

            // Reduce the remaining operations count
            k -= operations;
        }

        return score;
    }

private:
    // Helper function to compute the power of a number modulo MOD
    long long power(long long base, long long exponent) {
        long long res = 1;

        // Calculate the exponentiation using binary exponentiation
        while (exponent > 0) {
            // If the exponent is odd, multiply the result by the base
            if (exponent % 2 == 1) {
                res = ((res * base) % MOD);
            }

            // Square the base and halve the exponent
            base = (base * base) % MOD;
            exponent /= 2;
        }

        return res;
    }

    // Function to generate prime numbers up to a given limit using the Sieve of
    // Eratosthenes
    vector getPrimes(int limit) {
        vector isPrime(limit + 1, true);
        vector primes;

        // Start marking from the first prime number (2)
        for (int number = 2; number <= limit; number++) {
            if (!isPrime[number]) continue;

            // Store the prime number
            primes.push_back(number);

            // Mark multiples of the prime number as non-prime
            for (long long multiple = (long long)number * number;
                 multiple <= limit; multiple += number) {
                isPrime[multiple] = false;
            }
        }

        return primes;
    }
};