How hard is LeetCode 2818. Apply Operations to Maximize Score?

LeetCode 2818. Apply Operations to Maximize Score is rated Hard on LeetCode.

What is the time complexity of LeetCode 2818. Apply Operations to Maximize Score?

The Python solution on this page runs in O(n \times \log n).

What is the space complexity of LeetCode 2818. Apply Operations to Maximize Score?

The Python solution on this page uses O(n) auxiliary space.

What topics does LeetCode 2818. Apply Operations to Maximize Score cover?

LeetCode 2818. Apply Operations to Maximize Score is tagged Stack, Greedy, Array, Math, Number Theory, Sorting and Monotonic Stack on LeetCode.

Apply Operations to Maximize Score — LeetCode 2818 Python Solution

HardStackGreedyArrayMathNumber TheorySortingMonotonic Stack

Problem: #2818
Pattern: Stack
Reading time: 9 min
Source: leetcode.com

The problem

You are given an array nums of n positive integers and an integer k. Initially, you start with a score of 1.

Example

Input: nums = [8,3,9,3,8], k = 2
Output: 81
Explanation: To get a score of 81, we can apply the following operations:

Python solution

Python

def 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

Complexity

Measure	Complexity
Time	O(n \times \log n)
Space	O(n) auxiliary

Pattern: Stack

When the most recent unresolved thing is the one that matters, use a stack. LeetCode 2818. Apply Operations to Maximize Score is filed here because LeetCode tags it Stack, which is the vocabulary this hub collects.

The stack guide has the Python template for the pattern and the 194 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 2818. Apply Operations to Maximize Score?: LeetCode 2818. Apply Operations to Maximize Score is rated Hard on LeetCode.
What is the time complexity of LeetCode 2818. Apply Operations to Maximize Score?: The Python solution on this page runs in O(n \times \log n).
What is the space complexity of LeetCode 2818. Apply Operations to Maximize Score?: The Python solution on this page uses O(n) auxiliary space.
What topics does LeetCode 2818. Apply Operations to Maximize Score cover?: LeetCode 2818. Apply Operations to Maximize Score is tagged Stack, Greedy, Array, Math, Number Theory, Sorting and Monotonic Stack on LeetCode.