Apply Operations to Maximize Score

Hard

#2522Time: O(n^2 + M log log M), where n is the length of `nums` and M is the maximum value. The sieve takes O(M log log M). Calculating boundaries takes O(n^2). Sorting takes O(n log n). The final greedy selection takes O(n log k). The O(n^2) term dominates.Space: O(M + n), where M is the maximum value in `nums` and n is the length of `nums`. This is for the sieve array (`O(M)`), and various arrays of size `n` (prime scores, counts, indices).

Patterns

Math Greedy Number Theory

Algorithms

Sorting

Data structures

Array Stack Monotonic Stack

Prompt

You are given an array nums of n positive integers and an integer k.

Initially, you start with a score of 1. You have to maximize your score by applying the following operation at most k times:

Choose any non-empty subarray nums[l, ..., r] that you haven't chosen previously.
Choose an element x of nums[l, ..., r] with the highest prime score. If multiple such elements exist, choose the one with the smallest index.
Multiply your score by x.

Here, nums[l, ..., r] denotes the subarray of nums starting at index l and ending at the index r, both ends being inclusive.

The prime score of an integer x is equal to the number of distinct prime factors of x. For example, the prime score of 300 is 3 since 300 = 2 * 2 * 3 * 5 * 5.

Return the maximum possible score after applying at most k operations.

Since the answer may be large, return it modulo 10⁹+ 7.

Example 1:

Input: nums = [8,3,9,3,8], k = 2
Output: 81
Explanation: To get a score of 81, we can apply the following operations:
- Choose subarray nums[2, ..., 2]. nums[2] is the only element in this subarray. Hence, we multiply the score by nums[2]. The score becomes 1 * 9 = 9.
- Choose subarray nums[2, ..., 3]. Both nums[2] and nums[3] have a prime score of 1, but nums[2] has the smaller index. Hence, we multiply the score by nums[2]. The score becomes 9 * 9 = 81.
It can be proven that 81 is the highest score one can obtain.

Example 2:

Input: nums = [19,12,14,6,10,18], k = 3
Output: 4788
Explanation: To get a score of 4788, we can apply the following operations: 
- Choose subarray nums[0, ..., 0]. nums[0] is the only element in this subarray. Hence, we multiply the score by nums[0]. The score becomes 1 * 19 = 19.
- Choose subarray nums[5, ..., 5]. nums[5] is the only element in this subarray. Hence, we multiply the score by nums[5]. The score becomes 19 * 18 = 342.
- Choose subarray nums[2, ..., 3]. Both nums[2] and nums[3] have a prime score of 2, but nums[2] has the smaller index. Hence, we multipy the score by nums[2]. The score becomes 342 * 14 = 4788.
It can be proven that 4788 is the highest score one can obtain.

Constraints:

1 <= nums.length == n <= 10⁵
1 <= nums[i] <= 10⁵
1 <= k <= min(n * (n + 1) / 2, 10⁹)

Approaches

2 approaches with complexity analysis and trade-offs.

This approach revolves around a key insight: the problem can be broken down into determining, for each element nums[i], the total number of subarrays where it would be the chosen element. Once we have this count for every element, the problem becomes a greedy selection task. To maximize the product, we should multiply by the largest numbers as many times as possible. The number of times we can use nums[i] is precisely the number of subarrays where it's the 'best' element according to the problem's rules.

This specific version of the approach calculates these counts using a straightforward, but inefficient, brute-force method.

Algorithm

Pre-compute Prime Scores:
- Create an array primeScores of size max_val + 1, where max_val is the maximum possible value in nums (100001).
- Use a sieve method to populate this array. Iterate from i = 2 to max_val. If primeScores[i] is 0, i is a prime. Then, for all multiples of i (i.e., j = i, 2i, 3i, ...), increment primeScores[j].
Calculate Prime Scores for nums:
- Create an array ps of size n, where ps[i] = primeScores[nums[i]].
Calculate Contribution Counts (Naive):
- For each index i from 0 to n-1:
  - Find the left boundary L: Iterate j from i-1 down to 0. The first j where ps[j] >= ps[i] is L. If no such j exists, L = -1.
  - Find the right boundary R: Iterate j from i+1 up to n-1. The first j where ps[j] > ps[i] is R. If no such j exists, R = n.
  - The number of times nums[i] can be chosen is count[i] = (i - L) * (R - i).
Greedy Selection:
- Create an array of indices 0, 1, ..., n-1.
- Sort these indices in descending order based on the values in nums.
Calculate Final Score:
- Initialize score = 1.
- Iterate through the sorted indices. For each index i:
  - Determine how many times to take nums[i]: times_to_take = min(k, count[i]).
  - Update the score: score = (score * power(nums[i], times_to_take, MOD)) % MOD, where power is a modular exponentiation function.
  - Decrement k by times_to_take.
  - If k becomes 0, break the loop.
- Return the final score.

Walkthrough

The core of the algorithm is to first calculate the prime score for every number up to the maximum value in nums. This is done efficiently using a sieve. Then, for each element nums[i], we determine its 'dominance range'. An element nums[i] is chosen from a subarray [l, r] if it has the highest prime score, with ties broken by the smallest index. This translates to finding the nearest element to its left with a greater or equal prime score (L) and the nearest element to its right with a strictly greater prime score (R).

In this naive approach, we find L and R for each i by iterating through the array, which takes O(n) time for each element, leading to an overall O(n^2) complexity for this step. The number of subarrays that will select nums[i] is then (i - L) * (R - i).

After computing these counts for all elements, we have a collection of pairs (nums[i], count[i]). To maximize the final score, we greedily pick the largest numbers. We sort the elements nums[i] in descending order and, for each element, multiply it into our score min(k, count[i]) times, using modular exponentiation for efficiency. We continue this process until we have performed k operations.

1class Solution {2    public int maximumScore(int[] nums, int k) {3        int maxVal = 0;4        for (int num : nums) {5            maxVal = Math.max(maxVal, num);6        }7 8        int[] primeScores = new int[maxVal + 1];9        for (int i = 2; i <= maxVal; i++) {10            if (primeScores[i] == 0) { // i is prime11                for (long j = i; j <= maxVal; j += i) {12                    primeScores[(int)j]++;13                }14            }15        }16 17        int n = nums.length;18        int[] ps = new int[n];19        for (int i = 0; i < n; i++) {20            ps[i] = primeScores[nums[i]];21        }22 23        long[] counts = new long[n];24        for (int i = 0; i < n; i++) {25            int left = -1;26            for (int j = i - 1; j >= 0; j--) {27                if (ps[j] >= ps[i]) {28                    left = j;29                    break;30                }31            }32            int right = n;33            for (int j = i + 1; j < n; j++) {34                if (ps[j] > ps[i]) {35                    right = j;36                    break;37                }38            }39            counts[i] = (long)(i - left) * (right - i);40        }41 42        Integer[] indices = new Integer[n];43        for (int i = 0; i < n; i++) {44            indices[i] = i;45        }46        Arrays.sort(indices, (a, b) -> Integer.compare(nums[b], nums[a]));47 48        long score = 1;49        long MOD = 1_000_000_007;50 51        for (int i : indices) {52            if (k == 0) break;53            long num = nums[i];54            long count = counts[i];55            long timesToTake = Math.min(k, count);56            score = (score * power(num, timesToTake, MOD)) % MOD;57            k -= timesToTake;58        }59 60        return (int) score;61    }62 63    private long power(long base, long exp, long mod) {64        long res = 1;65        base %= mod;66        while (exp > 0) {67            if (exp % 2 == 1) res = (res * base) % mod;68            base = (base * base) % mod;69            exp /= 2;70        }71        return res;72    }73}

Complexity

Time

O(n^2 + M log log M), where n is the length of `nums` and M is the maximum value. The sieve takes O(M log log M). Calculating boundaries takes O(n^2). Sorting takes O(n log n). The final greedy selection takes O(n log k). The O(n^2) term dominates.

Space

O(M + n), where M is the maximum value in `nums` and n is the length of `nums`. This is for the sieve array (`O(M)`), and various arrays of size `n` (prime scores, counts, indices).

Trade-offs

Pros

The logic is straightforward and easier to reason about compared to more optimized solutions.
It correctly breaks down the problem into contribution counting and greedy selection.

Cons

The O(n^2) complexity for finding boundaries is too slow for the given constraints (n <= 10^5) and will result in a Time Limit Exceeded (TLE) error on most platforms.

This approach follows the same high-level strategy as the brute-force method: calculate the contribution count for each element and then apply a greedy strategy. However, it significantly optimizes the most expensive step—the calculation of contribution counts. Instead of using O(n^2) nested loops to find the dominance boundaries for each element, this method employs a monotonic stack. This data structure allows us to find the 'previous greater or equal' and 'next greater' elements for all items in the array in a single pass, reducing the time complexity of this critical step from O(n^2) to O(n).

Algorithm

Pre-compute Prime Scores: Same as the previous approach, using a sieve in O(M log log M) time.
Calculate Prime Scores for nums: Create an array ps of size n, where ps[i] = primeScores[nums[i]].
Optimized Boundary Calculation (Monotonic Stack):
- To find the left boundaries L[i] (previous greater or equal element) for all i, iterate from left to right using a monotonic stack. This takes O(n).
- To find the right boundaries R[i] (next greater element) for all i, iterate from right to left using a monotonic stack. This also takes O(n).
Calculate Contribution Counts: For each i, count[i] = (long)(i - L[i]) * (R[i] - i). This takes O(n).
Greedy Selection: Same as the previous approach. Sort indices based on nums values.
Calculate Final Score: Same as the previous approach. Iterate through sorted indices, apply modular exponentiation, and update k.

Walkthrough

The overall structure of the solution remains the same: pre-compute prime scores, find contribution counts, and then greedily select the largest numbers. The key improvement lies in how we find the left and right boundaries (L[i] and R[i]) for each element nums[i].

Finding Left Boundaries (L): We iterate through the ps (prime scores) array from left to right. We use a stack that stores indices j such that ps[j] is in non-increasing order. For each i, we pop elements from the stack as long as their prime score is less than ps[i]. The element remaining at the top of the stack is the first one to the left of i with a prime score greater than or equal to ps[i], which is our L[i].
Finding Right Boundaries (R): We do a similar pass from right to left. The stack will store indices j such that ps[j] is non-decreasing. For each i, we pop elements whose prime score is less than or equal to ps[i]. The top of the stack gives us the first element to the right of i with a strictly greater prime score, which is R[i].

Each index is pushed and popped at most once in each pass, making this step O(n). The rest of the algorithm, including sorting and the final product calculation, remains, but the overall complexity is now dominated by sorting, making it efficient enough for the given constraints.

1class Solution {2    public int maximumScore(int[] nums, int k) {3        int maxVal = 0;4        for (int num : nums) {5            maxVal = Math.max(maxVal, num);6        }7 8        int[] primeScores = new int[maxVal + 1];9        for (int i = 2; i <= maxVal; i++) {10            if (primeScores[i] == 0) { // i is prime11                for (long j = i; j <= maxVal; j += i) {12                    primeScores[(int)j]++;13                }14            }15        }16 17        int n = nums.length;18        int[] ps = new int[n];19        for (int i = 0; i < n; i++) {20            ps[i] = primeScores[nums[i]];21        }22 23        // Calculate left boundaries (previous greater or equal)24        int[] left = new int[n];25        Stack<Integer> stack = new Stack<>();26        for (int i = 0; i < n; i++) {27            while (!stack.isEmpty() && ps[stack.peek()] < ps[i]) {28                stack.pop();29            }30            left[i] = stack.isEmpty() ? -1 : stack.peek();31            stack.push(i);32        }33 34        // Calculate right boundaries (next greater)35        int[] right = new int[n];36        stack.clear();37        for (int i = n - 1; i >= 0; i--) {38            while (!stack.isEmpty() && ps[stack.peek()] <= ps[i]) {39                stack.pop();40            }41            right[i] = stack.isEmpty() ? n : stack.peek();42            stack.push(i);43        }44 45        long[] counts = new long[n];46        for (int i = 0; i < n; i++) {47            counts[i] = (long)(i - left[i]) * (right[i] - i);48        }49 50        Integer[] indices = new Integer[n];51        for (int i = 0; i < n; i++) {52            indices[i] = i;53        }54        Arrays.sort(indices, (a, b) -> Integer.compare(nums[b], nums[a]));55 56        long score = 1;57        long MOD = 1_000_000_007;58 59        for (int i : indices) {60            if (k == 0) break;61            long num = nums[i];62            long count = counts[i];63            long timesToTake = Math.min(k, count);64            score = (score * power(num, timesToTake, MOD)) % MOD;65            k -= timesToTake;66        }67 68        return (int) score;69    }70 71    private long power(long base, long exp, long mod) {72        long res = 1;73        base %= mod;74        while (exp > 0) {75            if (exp % 2 == 1) res = (res * base) % mod;76            base = (base * base) % mod;77            exp /= 2;78        }79        return res;80    }81}

Complexity

Time

O(n log n + M log log M + n log k). Sieve is O(M log log M). The monotonic stack part is O(n). Sorting is O(n log n). The final loop is O(n log k). This is dominated by O(n log n) or O(M log log M) depending on the inputs.

Space

O(M + n), where M is the maximum value in `nums` and n is the length of `nums`. Space is used for the sieve, prime score arrays, monotonic stack, and boundary arrays.

Trade-offs

Pros

Highly efficient, with a time complexity that meets the problem constraints.
It's a classic and powerful application of the monotonic stack pattern for range-based problems.

Cons

The logic involving the monotonic stack can be less intuitive to come up with and implement correctly compared to the naive O(n^2) loops.

Solutions

Solution

1class Solution {2private3  final int mod = (int)1 e9 + 7;4public5  int maximumScore(List<Integer> nums, int k) {6    int n = nums.size();7    int[][] arr = new int[n][0];8    for (int i = 0; i < n; ++i) {9      arr[i] = new int[]{i, primeFactors(nums.get(i)), nums.get(i)};10    }11    int[] left = new int[n];12    int[] right = new int[n];13    Arrays.fill(left, -1);14    Arrays.fill(right, n);15    Deque<Integer> stk = new ArrayDeque<>();16    for (int[] e : arr) {17      int i = e[0], f = e[1];18      while (!stk.isEmpty() && arr[stk.peek()][1] < f) {19        stk.pop();20      }21      if (!stk.isEmpty()) {22        left[i] = stk.peek();23      }24      stk.push(i);25    }26    stk.clear();27    for (int i = n - 1; i >= 0; --i) {28      int f = arr[i][1];29      while (!stk.isEmpty() && arr[stk.peek()][1] <= f) {30        stk.pop();31      }32      if (!stk.isEmpty()) {33        right[i] = stk.peek();34      }35      stk.push(i);36    }37    Arrays.sort(arr, (a, b)->b[2] - a[2]);38    long ans = 1;39    for (int[] e : arr) {40      int i = e[0], x = e[2];41      int l = left[i], r = right[i];42      long cnt = (long)(i - l) * (r - i);43      if (cnt <= k) {44        ans = ans * qpow(x, cnt) % mod;45        k -= cnt;46      } else {47        ans = ans * qpow(x, k) % mod;48        break;49      }50    }51    return (int)ans;52  }53private54  int primeFactors(int n) {55    int i = 2;56    Set<Integer> ans = new HashSet<>();57    while (i <= n / i) {58      while (n % i == 0) {59        ans.add(i);60        n /= i;61      }62      ++i;63    }64    if (n > 1) {65      ans.add(n);66    }67    return ans.size();68  }69private70  int qpow(long a, long n) {71    long ans = 1;72    for (; n > 0; n >>= 1) {73      if ((n & 1) == 1) {74        ans = ans * a % mod;75      }76      a = a * a % mod;77    }78    return (int)ans;79  }80}

1class Solution {2public:3  int maximumScore(vector<int> &nums, int k) {4    const int mod = 1e9 + 7;5    int n = nums.size();6    vector<tuple<int, int, int>> arr(n);7    for (int i = 0; i < n; ++i) {8      arr[i] = {i, primeFactors(nums[i]), nums[i]};9    }10    vector<int> left(n, -1);11    vector<int> right(n, n);12    stack<int> stk;13    for (auto [i, f, _] : arr) {14      while (!stk.empty() && get<1>(arr[stk.top()]) < f) {15        stk.pop();16      }17      if (!stk.empty()) {18        left[i] = stk.top();19      }20      stk.push(i);21    }22    stk = stack<int>();23    for (int i = n - 1; ~i; --i) {24      int f = get<1>(arr[i]);25      while (!stk.empty() && get<1>(arr[stk.top()]) <= f) {26        stk.pop();27      }28      if (!stk.empty()) {29        right[i] = stk.top();30      }31      stk.push(i);32    }33    sort(arr.begin(), arr.end(), [](const auto &lhs, const auto &rhs) {34      return get<2>(rhs) < get<2>(lhs);35    });36    long long ans = 1;37    auto qpow = [&](long long a, int n) {38      long long ans = 1;39      for (; n; n >>= 1) {40        if (n & 1) {41          ans = ans * a % mod;42        }43        a = a * a % mod;44      }45      return ans;46    };47    for (auto [i, _, x] : arr) {48      int l = left[i], r = right[i];49      long long cnt = 1LL * (i - l) * (r - i);50      if (cnt <= k) {51        ans = ans * qpow(x, cnt) % mod;52        k -= cnt;53      } else {54        ans = ans * qpow(x, k) % mod;55        break;56      }57    }58    return ans;59  }60  int primeFactors(int n) {61    int i = 2;62    unordered_set<int> ans;63    while (i <= n / i) {64      while (n % i == 0) {65        ans.insert(i);66        n /= i;67      }68      ++i;69    }70    if (n > 1) {71      ans.insert(n);72    }73    return ans.size();74  }75};

1def primeFactors ( n ): i = 2 ans = set () while i * i <= n : while n % i == 0 : ans . add ( i ) n //= i i += 1 if n > 1 : ans . add ( n ) return len ( ans ) class Solution : def maximumScore ( self , nums : List [ int ], k : int ) -> int : mod = 10 ** 9 + 7 arr = [( i , primeFactors ( x ), x ) for i , x in enumerate ( nums )] n = len ( nums ) left = [ - 1 ] * n right = [ n ] * n stk = [] for i , f , x in arr : while stk and stk [ - 1 ][ 0 ] < f : stk . pop () if stk : left [ i ] = stk [ - 1 ][ 1 ] stk . append (( f , i )) stk = [] for i , f , x in arr [:: - 1 ]: while stk and stk [ - 1 ][ 0 ] <= f : stk . pop () if stk : right [ i ] = stk [ - 1 ][ 1 ] stk . append (( f , i )) arr . sort ( key = lambda x : - x [ 2 ]) ans = 1 for i , f , x in arr : l , r = left [ i ], right [ i ] cnt = ( i - l ) * ( r - i ) if cnt <= k : ans = ans * pow ( x , cnt , mod ) % mod k -= cnt else : ans = ans * pow ( x , k , mod ) % mod break return ans

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem