LeetCode, Hard: 2818. Apply Operations to Maximize Score. Swift

Description

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^9 + 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^5
1 <= nums[i] <= 10^5
1 <= k <= min(n * (n + 1) / 2, 10^9)

Approach

1 Compute Prime Scores:

• Calculate the prime score for each integer in the array nums. Prime score represents the number of distinct prime factors of an integer.

• Initialize a boolean array prime of size upper, where upper is the maximum element in nums plus 1.

• Initialize an integer array primeScore of the same size.

• Set prime[0] and prime[1] to false.

• Iterate over integers from 2 to upper — 1, and update primeScore and prime based on their prime factors.

2 Compute Next Greater Elements:

• Initialize arrays nextGreaterElement and prevGreaterOrEqualElement of size n, where n is the length of nums.

• Use a monotonic stack to find the next greater element with a greater prime score for each element in nums.

• Iterate through nums and maintain a stack of indices.

• For each element, pop elements from the stack if their prime score is less than or equal to the current element’s prime score.

• Record the index of the top of the stack as the nextGreaterElement if the stack is not empty, else set it to n.

• Repeat the above process in reverse to compute prevGreaterOrEqualElement.

3 Sort and Process Elements:

• Create an array of tuples (num, i) where num is the value of an element and i is its index in nums.

• Sort the tuples in descending order of the first element (num).

• Loop through the sorted tuples and perform the following steps:

  • Compute the number of operations as the minimum of (i — prevGreaterOrEqualElement[i]) * (nextGreaterElement[i] — i) and k.

  • Update res by multiplying it with pow(num, operations) modulo MOD using the helper function pow.

  • Decrement k by the number of operations.

  • If k becomes 0, return res.

4 Helper Function for Exponentiation:

• Implement the pow function to calculate exponentiation efficiently using modular arithmetic.

Complexity

• Time complexity: O(max(nums) * log(max(nums)) + n * log(n)). Accounting for computing prime scores, using the stack to compute next greater elements, and sorting the tuples.

• Space complexity: O(max(nums) + n). Considering the space required for arrays and the stack used for computation.

Code (Swift)

class Solution {      func maximumScore(_ nums: [Int], _ k: Int) -> Int {         let MOD = 1_000_000_007         var k = k  // Make a mutable copy of k         let n = nums.count          var upper = nums.max()! + 1          var prime = [Bool](repeating: true, count: upper)         prime[0] = false         prime[1] = false         var primeScore = [Int](repeating: 0, count: upper)          for i in 2..<upper {             if prime[i] {                 var j = i                 while j < upper {                     primeScore[j] += 1                     prime[j] = false                     j += i                 }             }         }          var nextGreaterElement = [Int](repeating: n, count: n)         var s = [Int]()         for i in (0..<n).reversed() {             while !s.isEmpty && primeScore[nums[i]] >= primeScore[nums[s.last!]] {                 s.popLast()             }             nextGreaterElement[i] = s.isEmpty ? n : s.last!             s.append(i)         }          var prevGreaterOrEqualElement = [Int](repeating: -1, count: n)         s.removeAll()         for i in 0..<n {             while !s.isEmpty && primeScore[nums[i]] > primeScore[nums[s.last!]] {                 s.popLast()             }             prevGreaterOrEqualElement[i] = s.isEmpty ? -1 : s.last!             s.append(i)         }          var res = 1         var tuples = [(num: Int, index: Int)]()         for i in 0..<n {             tuples.append((nums[i], i))         }         tuples.sort { a, b in             a.num > b.num         }          for (num, i) in tuples {             let operations = min(                 (i - prevGreaterOrEqualElement[i]) * (nextGreaterElement[i] - i), k)             res = (res * pow(num, operations, MOD)) % MOD             k -= operations             if k == 0 {                 return res             }         }          return res     }      func pow(_ x: Int, _ n: Int, _ mod: Int) -> Int {         var res = 1         var x = x         var n = n         while n > 0 {             if n % 2 == 1 {                 res = (res * x) % mod             }             x = (x * x) % mod             n /= 2         }         return res     } }

Source: Github