LeetCode, Hard: 2818. Apply Operations to Maximize Score. Swift
Tags: swift, ios, programming, algorithms
Published: 2023-08-19 17:01:10

## 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)
```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](https://github.com/sergeyleschev/leetcode-swift/blob/main/2501-3000/2818.%20Apply%20Operations%20to%20Maximize%20Score.swift)


[![Sergey Leschev LeetCode Global TOP 200](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/d81vvhe4jc5uz2qa834y.jpg)](https://github.com/sergeyleschev)

---

**Contacts**
I have a clear focus on time-to-market and don't prioritize technical debt. And I took part in the Pre-Sale/RFX activity as a System Architect, assessment efforts for Mobile (iOS-Swift, Android-Kotlin), Frontend (React-TypeScript) and Backend (NodeJS-.NET-PHP-Kafka-SQL-NoSQL). And I also formed the work of Pre-Sale as a CTO from Opportunity to Proposal via knowledge transfer to Successful Delivery.

🛩️ #startups #management #cto #swift #typescript #database
📧 Email: sergey.leschev@gmail.com
👋 LinkedIn: https://linkedin.com/in/sergeyleschev/
👋 LeetCode: https://leetcode.com/sergeyleschev/
👋 Twitter: https://twitter.com/sergeyleschev
👋 Github: https://github.com/sergeyleschev
🌎 Website: https://sergeyleschev.github.io
🌎 Reddit: https://reddit.com/user/sergeyleschev
🌎 Quora: https://quora.com/sergey-leschev
🌎 Medium: https://medium.com/@sergeyleschev
🖨️ PDF Design Patterns: [Download](https://sergeyleschev.github.io/sergeyleschev-design-patterns.pdf)